首先要對輸入資料進行處理

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

我是輸入往輸出走

算延遲是輸出往輸入

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

我是輸入往輸出走

算延遲是輸出往輸入

我的程式碼(算延遲有改過 併入算邏輯的迴圈)

 

我的程式碼(算延遲有改過 併入算邏輯的迴圈)

def main():

    from sys import stdin

    p,q,r,m=map(int,stdin.readline().split())

    state=[0 for _ in range(p+q+r+1)]#0 1狀態

    lef=state.copy()#剩餘輸入數量

    md=state.copy()#最大距離

    state[1:p+1]=map(int,stdin.readline().split())#獲取輸入

    typ=tuple(map(int,stdin.readline().split()))#種類0 buffer 1 and 2 or 3 XOR 4 NOT

    key=[[] for _ in range(p+q+r+1)]#輸入往輸出的編號

    con=[[] for _ in range(p+q+r+1)]#輸出往輸入的編號

    for _ in range(m):

        a,b=map(int,stdin.readline().split())

        lef[b]+=1#剩餘輸入數量+1

        key[a].append(b)#連接

        if p+q+1>b>p or con[b]==[]:con[b].append(a)#連接 前面判斷式可不寫 用來加速用

    t=[(i,0) for i in range(1,p+1)]

    while t:

        idx,dis=t.pop()

        for kid in key[idx]:#輸入端連接到的

            lef[kid]-=1

            if dis>md[kid]:md[kid]=dis#最大距離

            if lef[kid]==0:#如果閘的輸入01狀態都知道了

                t.append((kid,md[kid]+1))#新增到stack

                if p+q>=kid>p:tk=typ[kid-p-1]#如果是邏輯閘 則對應到typ

                else:tk=0#否則都是buffer或無功能

                if tk==0:

                    state[kid]=state[con[kid][0]]

                elif tk==1:

                    state[kid]=0

                    for j in con[kid]:

                        if state[j]==0:break

                    else:state[kid]=1

                elif tk==2:

                    state[kid]=1

                    for j in con[kid]:

                        if state[j]:break

                    else:state[kid]=0

                elif tk==3:

                    f=0

                    for j in con[kid]:

                        if state[j]:f+=1

                    state[kid]=f%2

                elif tk==4:

                    state[kid]=0 if state[con[kid][0]] else 1

    print(max(md[p+q+1:]))

    print(*state[p+q+1:])

if __name__=="__main__":main()

我的類似 開啟寶盒 的做法

 

我的程式碼(算延遲有改過 併入算邏輯的迴圈)

def main():

    from sys import stdin

    p,q,r,m=map(int,stdin.readline().split())

    state=[0 for _ in range(p+q+r+1)]#0 1狀態

    lef=state.copy()#剩餘輸入數量

    md=state.copy()#最大距離

    state[1:p+1]=map(int,stdin.readline().split())#獲取輸入

    typ=tuple(map(int,stdin.readline().split()))#種類0 buffer 1 and 2 or 3 XOR 4 NOT

    key=[[] for _ in range(p+q+r+1)]#輸入往輸出的編號

    con=[[] for _ in range(p+q+r+1)]#輸出往輸入的編號

    for _ in range(m):

        a,b=map(int,stdin.readline().split())

        lef[b]+=1#剩餘輸入數量+1

        key[a].append(b)#連接

        if p+q+1>b>p or con[b]==[]:con[b].append(a)#連接 前面判斷式可不寫 用來加速用

    t=[(i,0) for i in range(1,p+1)]

    while t:

        idx,dis=t.pop()

        for kid in key[idx]:#輸入端連接到的

            lef[kid]-=1

            if dis>md[kid]:md[kid]=dis#最大距離

            if lef[kid]==0:#如果閘的輸入01狀態都知道了

                t.append((kid,md[kid]+1))#新增到stack

                if p+q>=kid>p:tk=typ[kid-p-1]#如果是邏輯閘 則對應到typ

                else:tk=0#否則都是buffer或無功能

                if tk==0:

                    state[kid]=state[con[kid][0]]

                elif tk==1:

                    state[kid]=0

                    for j in con[kid]:

                        if state[j]==0:break

                    else:state[kid]=1

                elif tk==2:

                    state[kid]=1

                    for j in con[kid]:

                        if state[j]:break

                    else:state[kid]=0

                elif tk==3:

                    f=0

                    for j in con[kid]:

                        if state[j]:f+=1

                    state[kid]=f%2

                elif tk==4:

                    state[kid]=0 if state[con[kid][0]] else 1

    print(max(md[p+q+1:]))

    print(*state[p+q+1:])

if __name__=="__main__":main()

我的類似 開啟寶盒 的做法

我剛剛把con刪掉了 空間會少一點

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

 

我用python寫 也是從輸入點用DFS走訪到輸出點 並記錄最大延遲還有記錄各點的值
但只拿到10% 後面都TLE 
請問怎麼各位大神怎麼優化的🙏

 

    

 

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

 

 

    

 

我用python寫 也是從輸入點用DFS走訪到輸出點 並記錄最大延遲還有記錄各點的值
但只拿到10% 後面都TLE 
請問怎麼各位大神怎麼優化的🙏

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

 

 

    

 

我用python寫 也是從輸入點用DFS走訪到輸出點 並記錄最大延遲還有記錄各點的值
但只拿到10% 後面都TLE 
請問怎麼各位大神怎麼優化的🙏

程式碼？

你可能時間複雜度太高

首先要對輸入資料進行處理

p,q,r,m = map(int,input().split())

ip = [int(x) for x in input().split()]   #記錄各輸入點的值

gc = [int(x) for x in input().split()]  #記錄各邏輯閘的種類

g  = [[-1,-1,0] for i in range(q)] #[a輸入端 b輸入端 Logic gates] -1=無

gv = [-1 for i in range(q)] #紀錄個邏輯閘輸出值

out = []    #紀錄輸出點 並由小到大排序

to =[[] for i in range(m+1)]    #記錄各點之間的關係

 

邊輸入邊處理邏輯閘的數據

for i in range(m):

    a,b = map(int,input().split())

    if b>p+q:

        out.append([a,b])

    elif b>p and b<=p+q:

        temp =b-(p+1)

        g[temp][2] = gc[temp]

        if g[temp][0]==-1:

            g[temp][0] = a

        else:

            g[temp][1] = a

    to[b].append(a)

out.sort(key=lambda x:x[1])

 

這邊主要由輸出端往輸入端走訪 (如果從輸入端往輸出端走訪記錄延遲，會有邏輯閘空接的狀況)

 

(請自行設計迴圈搭配find)

#由output -> gate -> input 走訪記錄 最大延遲

ans = 0 #設定一個delay最大值的紀錄

def find(now,dp):

    global ans

    dp+=1

    for i in to[now]:

        if i>p:

            find(i,dp)

    ans = max(ans,dp)

    return

 

#取得個邏輯閘輸出值

這邊可以設計自訂函數傳入(接點a ,接點b,邏輯閘種類)

 

提示:判斷接點為 前p個輸入點 或是 邏輯閘的輸出

若是邏輯閘的輸出端點 可用gv[index] 去查找該點的值為何

若尚未計算 則是將該接點編號-p 透過g[index]查找該邏輯閘

並將資料傳入函數內計算以此類推。 

 

#最後整理輸出值

 

 

    

 

我用python寫 也是從輸入點用DFS走訪到輸出點 並記錄最大延遲還有記錄各點的值
但只拿到10% 後面都TLE 
請問怎麼各位大神怎麼優化的🙏

程式碼？

你可能時間複雜度太高

程式碼在這 再請各位大神給意見🙏
然後我上面好像打錯了 我是從輸出點走訪到輸入點 跟原po一樣

有沒有可能 有一條線 連接到 多個輸出閘

這條線往輸入的地方又有大量的路徑？

你可以多一個判斷

DFS如果value已經改過了 直接return

 

有沒有可能 有一條線 連接到 多個輸出閘

這條線往輸入的地方又有大量的路徑？

你可以多一個判斷

DFS如果value已經改過了 直接return

可以把value預設改為-1

0 1代表已經確定狀態

我晚點再測試看看

 

有沒有可能 有一條線 連接到 多個輸出閘

這條線往輸入的地方又有大量的路徑？

你可以多一個判斷

DFS如果value已經改過了 直接return

可以把value預設改為-1

0 1代表已經確定狀態

我晚點再測試看看

Worst case 5×10^3 output×(5×10^4 gate +10^3 input)

 

有沒有可能 有一條線 連接到 多個輸出閘

這條線往輸入的地方又有大量的路徑？

你可以多一個判斷

DFS如果value已經改過了 直接return

可以把value預設改為-1

0 1代表已經確定狀態

我晚點再測試看看

Worst case 5×10^3 output×(5×10^4 gate +10^3 input)

你的程式碼只要改一行 + 新增一行就過了

 

有沒有可能 有一條線 連接到 多個輸出閘

這條線往輸入的地方又有大量的路徑？

你可以多一個判斷

DFS如果value已經改過了 直接return

可以把value預設改為-1

0 1代表已經確定狀態

我晚點再測試看看

Worst case 5×10^3 output×(5×10^4 gate +10^3 input)

你的程式碼只要改一行 + 新增一行就過了

幹真的AC了 感謝哥 你是我的神🙏
不知道原來差這個判斷差那麼多