結果
問題 | No.2160 みたりのDominator |
ユーザー | googol_S0 |
提出日時 | 2022-12-11 03:13:54 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,874 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 322,544 KB |
最終ジャッジ日時 | 2024-10-15 02:49:36 |
合計ジャッジ時間 | 49,379 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 49 ms
54,528 KB |
testcase_01 | AC | 1,095 ms
306,648 KB |
testcase_02 | AC | 44 ms
54,272 KB |
testcase_03 | AC | 49 ms
55,416 KB |
testcase_04 | AC | 46 ms
55,252 KB |
testcase_05 | WA | - |
testcase_06 | AC | 50 ms
55,040 KB |
testcase_07 | AC | 51 ms
56,320 KB |
testcase_08 | AC | 65 ms
65,792 KB |
testcase_09 | AC | 67 ms
66,816 KB |
testcase_10 | AC | 65 ms
65,792 KB |
testcase_11 | AC | 66 ms
66,432 KB |
testcase_12 | AC | 65 ms
65,536 KB |
testcase_13 | AC | 52 ms
55,808 KB |
testcase_14 | AC | 52 ms
56,320 KB |
testcase_15 | AC | 49 ms
55,680 KB |
testcase_16 | AC | 70 ms
67,328 KB |
testcase_17 | AC | 64 ms
65,792 KB |
testcase_18 | AC | 70 ms
67,456 KB |
testcase_19 | AC | 71 ms
67,840 KB |
testcase_20 | AC | 73 ms
68,864 KB |
testcase_21 | AC | 71 ms
67,456 KB |
testcase_22 | AC | 70 ms
67,328 KB |
testcase_23 | AC | 84 ms
70,656 KB |
testcase_24 | AC | 51 ms
55,680 KB |
testcase_25 | AC | 55 ms
57,088 KB |
testcase_26 | AC | 68 ms
65,536 KB |
testcase_27 | AC | 54 ms
56,320 KB |
testcase_28 | AC | 52 ms
55,808 KB |
testcase_29 | AC | 51 ms
55,808 KB |
testcase_30 | AC | 52 ms
55,936 KB |
testcase_31 | AC | 51 ms
55,296 KB |
testcase_32 | AC | 52 ms
56,064 KB |
testcase_33 | AC | 46 ms
54,400 KB |
testcase_34 | AC | 937 ms
296,628 KB |
testcase_35 | AC | 45 ms
54,528 KB |
testcase_36 | AC | 48 ms
54,528 KB |
testcase_37 | AC | 46 ms
54,784 KB |
testcase_38 | AC | 47 ms
54,784 KB |
testcase_39 | AC | 48 ms
55,040 KB |
testcase_40 | AC | 1,142 ms
296,284 KB |
testcase_41 | AC | 1,157 ms
296,952 KB |
testcase_42 | AC | 754 ms
233,744 KB |
testcase_43 | AC | 925 ms
277,272 KB |
testcase_44 | AC | 1,172 ms
322,544 KB |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | AC | 790 ms
251,852 KB |
testcase_52 | AC | 1,078 ms
311,392 KB |
testcase_53 | AC | 1,127 ms
319,884 KB |
testcase_54 | AC | 728 ms
224,148 KB |
testcase_55 | AC | 763 ms
247,592 KB |
testcase_56 | AC | 699 ms
239,504 KB |
testcase_57 | AC | 723 ms
250,480 KB |
testcase_58 | AC | 787 ms
263,308 KB |
testcase_59 | AC | 749 ms
249,028 KB |
testcase_60 | AC | 716 ms
261,612 KB |
testcase_61 | AC | 750 ms
256,196 KB |
testcase_62 | AC | 859 ms
263,416 KB |
testcase_63 | AC | 763 ms
251,832 KB |
testcase_64 | AC | 690 ms
243,760 KB |
testcase_65 | AC | 437 ms
158,168 KB |
testcase_66 | AC | 473 ms
165,560 KB |
testcase_67 | AC | 496 ms
168,832 KB |
testcase_68 | AC | 795 ms
252,908 KB |
testcase_69 | AC | 607 ms
193,084 KB |
testcase_70 | AC | 776 ms
249,812 KB |
testcase_71 | AC | 383 ms
143,952 KB |
testcase_72 | AC | 567 ms
192,464 KB |
testcase_73 | AC | 816 ms
251,828 KB |
testcase_74 | AC | 781 ms
247,612 KB |
testcase_75 | AC | 244 ms
119,628 KB |
testcase_76 | AC | 205 ms
108,752 KB |
testcase_77 | AC | 489 ms
179,844 KB |
testcase_78 | AC | 574 ms
199,048 KB |
testcase_79 | AC | 280 ms
104,368 KB |
testcase_80 | AC | 314 ms
103,044 KB |
testcase_81 | AC | 483 ms
130,424 KB |
testcase_82 | AC | 430 ms
136,236 KB |
testcase_83 | AC | 283 ms
137,780 KB |
61_evil_bias_nocross_01.txt | AC | 1,174 ms
329,200 KB |
61_evil_bias_nocross_02.txt | AC | 1,148 ms
298,520 KB |
61_evil_bias_nocross_03.txt | AC | 731 ms
240,136 KB |
61_evil_bias_nocross_04.txt | AC | 915 ms
278,940 KB |
61_evil_bias_nocross_05.txt | AC | 1,097 ms
309,888 KB |
61_evil_bias_nocross_06.txt | AC | 1,145 ms
300,556 KB |
61_evil_bias_nocross_07.txt | AC | 799 ms
252,616 KB |
61_evil_bias_nocross_08.txt | AC | 1,056 ms
310,236 KB |
61_evil_bias_nocross_09.txt | AC | 1,115 ms
285,576 KB |
61_evil_bias_nocross_10.txt | AC | 671 ms
226,256 KB |
61_evil_bias_nocross_11.txt | AC | 882 ms
274,108 KB |
61_evil_bias_nocross_12.txt | AC | 1,043 ms
297,728 KB |
ソースコード
from bisect import * def scc(N,edges): M=len(edges) start=[0]*(N+1) elist=[0]*M for e in edges: start[e[0]+1]+=1 for i in range(1,N+1): start[i]+=start[i-1] counter=start[:] for e in edges: elist[counter[e[0]]]=e[1] counter[e[0]]+=1 visited=[] low=[0]*N Ord=[-1]*N ids=[0]*N NG=[0,0] def dfs(v): stack=[(v,-1,0),(v,-1,1)] while stack: v,bef,t=stack.pop() if t: if bef!=-1 and Ord[v]!=-1: low[bef]=min(low[bef],Ord[v]) stack.pop() continue low[v]=NG[0] Ord[v]=NG[0] NG[0]+=1 visited.append(v) for i in range(start[v],start[v+1]): to=elist[i] if Ord[to]==-1: stack.append((to,v,0)) stack.append((to,v,1)) else: low[v]=min(low[v],Ord[to]) else: if low[v]==Ord[v]: while(True): u=visited.pop() Ord[u]=N ids[u]=NG[1] if u==v: break NG[1]+=1 low[bef]=min(low[bef],low[v]) for i in range(N): if Ord[i]==-1: dfs(i) for i in range(N): ids[i]=NG[1]-1-ids[i] group_num=NG[1] counts=[0]*group_num for x in ids: counts[x]+=1 groups=[[] for i in range(group_num)] for i in range(N): groups[ids[i]].append(i) return groups N1,N2,N3,M=map(int,input().split()) NN=[N1+2,N2+2,N3+2] NNN=[0,N1+2,N1+N2+4,N1+N2+N3+6] K=N1+N2+N3 N=K+6 X=[] E=[(0,N1+2),(N1+2,N1+N2+4),(N1+1,N1+N2+3),(N1+N2+3,N1+N2+N3+5)] C=[] for i in range(N1+2): C.append(1) for i in range(N2+2): C.append(2) for i in range(N3+2): C.append(3) for i in range(4): E.append((E[i][1],E[i][0])) for i in range(N1+1): E.append((i+1,i)) for i in range(N2+1): i+=N1+2 E.append((i+1,i)) for i in range(N3+1): i+=N1+N2+4 E.append((i+1,i)) for i in range(M): u,v=map(int,input().split()) X.append((u,v)) u-=1 v-=1 if u<N1: u+=1 elif u<N1+N2: u+=3 elif u<N1+N2+N3: u+=5 elif u==K: u=0 else: u=N-1 u,v=v,u if u<N1: u+=1 elif u<N1+N2: u+=3 elif u<N1+N2+N3: u+=5 elif u==K: u=0 else: u=N-1 E.append((u,v)) E.append((v,u)) S=scc(N,E) L=len(S) V=[0]*L P=[[1234567,-1,1234567,-1,1234567,-1] for i in range(L)] for i in range(L): for j in range(len(S[i])): v=S[i][j] c=C[v] if c==3: V[i]|=4 else: V[i]|=c w=c-1 P[i][w*2]=min(P[i][w*2],v) P[i][w*2+1]=max(P[i][w*2+1],v) P[i]=tuple(P[i]) Q=[] R=[[],[],[]] for i in range(L): if V[i]==7: Q.append(P[i]) for j in range(3): R[j].append((P[i][2*j],P[i][2*j+1])) for j in range(3): if P[i][j*2+1]-P[i][j*2]==NN[j]-1: print(0) exit() for i in range(3): R[i].sort() T=[[] for i in range(len(R[0]))] for i in range(L): if V[i]==7: continue if P[i][1]!=-1: v=bisect_left(R[0],(P[i][0],P[i][1]))-1 T[v].append(P[i]) elif P[i][3]!=-1: v=bisect_left(R[1],(P[i][2],P[i][3]))-1 T[v].append(P[i]) else: v=bisect_left(R[2],(P[i][4],P[i][5]))-1 T[v].append(P[i]) ANS=0 for I in range(len(T)-1): Y=[[R[0][I][1]+1,R[0][I+1][0]],[R[1][I][1]+1,R[1][I+1][0]],[R[2][I][1]+1,R[2][I+1][0]]] Z=[[],[],[]] ZZ=[[],[],[]] for i in range(3): for j in range(Y[i][0],Y[i][1]): Z[i].append((0,-1,-1)) ZZ[i].append((i+1)*1000000+j) ZZ[i].append((i+1)*1000000+500000) for i in range(len(T[I])): if T[I][i][1]>=0 and T[I][i][3]>=0: v=T[I][i][1]-Y[0][0] w=T[I][i][3]-Y[1][0] Z[0][v]=(Z[0][v][0],1,w) Z[1][w]=(Z[1][w][0],0,v) ZZ[0][v]=i ZZ[1][w]=i elif T[I][i][1]>=0 and T[I][i][5]>=0: v=T[I][i][1]-Y[0][0] w=T[I][i][5]-Y[2][0] Z[0][v]=(Z[0][v][0],2,w) Z[2][w]=(Z[2][w][0],0,v) ZZ[0][v]=i ZZ[2][w]=i elif T[I][i][3]>=0 and T[I][i][5]>=0: v=T[I][i][3]-Y[1][0] w=T[I][i][5]-Y[2][0] Z[1][v]=(Z[1][v][0],2,w) Z[2][w]=(Z[2][w][0],1,v) ZZ[1][v]=i ZZ[2][w]=i for j in range(3): if T[I][i][j*2]<T[I][i][j*2+1]: for k in range(T[I][i][j*2]+1,T[I][i][j*2+1]+1): k-=Y[j][0] Z[j][k]=(1,Z[j][k][1],Z[j][k][2]) W=[] a,b,c=Y[0][1]-Y[0][0],Y[1][1]-Y[1][0],Y[2][1]-Y[2][0] W=[(a,b,c,0)] abc=[a,b,c] while a+b+c>0: if a>0: if a==Y[0][1]-Y[0][0]: a-=1 abc[0]-=1 W.append((a,b,c,0)) continue if not(Z[0][a][1]!=-1 and abc[Z[0][a][1]]>Z[0][a][2]): a-=1 abc[0]-=1 W.append((a,b,c,0)) continue if b>0: if b==Y[1][1]-Y[1][0]: b-=1 abc[1]-=1 W.append((a,b,c,1)) continue if not(Z[1][b][1]!=-1 and abc[Z[1][b][1]]>Z[1][b][2]): b-=1 abc[1]-=1 W.append((a,b,c,1)) continue c-=1 abc[2]-=1 W.append((a,b,c,2)) for i in range(len(W)): W[i]=list(W[i]) if ZZ[0][W[i][0]]==ZZ[1][W[i][1]]: W[i].append(0b10011001) elif ZZ[0][W[i][0]]==ZZ[2][W[i][2]]: W[i].append(0b10100101) elif ZZ[1][W[i][1]]==ZZ[2][W[i][2]]: W[i].append(0b11000011) else: W[i].append(0b11111111) W[i]=tuple(W[i]) dp=[[0]*8 for i in range(len(W))] dp[0][7]=1 for i in range(len(W)-1): for j in range(8): jj=j&(~(1<<W[i+1][3])) kk=(jj^j)>>W[i+1][3] for k in range(kk+1): jjj=jj|(k<<W[i+1][3]) if (W[i+1][4]>>jjj)&1 and ((kk^k)==0 or Z[W[i+1][3]][W[i+1][W[i+1][3]]][0]==0): dp[i+1][jjj]+=dp[i][j] ANS+=sum(dp[-1]) print(ANS)