結果
問題 | No.2160 みたりのDominator |
ユーザー | googol_S0 |
提出日時 | 2022-12-11 03:16:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,095 ms / 2,000 ms |
コード長 | 5,899 bytes |
コンパイル時間 | 725 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 320,568 KB |
最終ジャッジ日時 | 2024-06-24 22:55:53 |
合計ジャッジ時間 | 46,613 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,972 KB |
testcase_01 | AC | 1,039 ms
305,672 KB |
testcase_02 | AC | 40 ms
55,876 KB |
testcase_03 | AC | 43 ms
55,556 KB |
testcase_04 | AC | 44 ms
55,724 KB |
testcase_05 | AC | 43 ms
55,800 KB |
testcase_06 | AC | 44 ms
56,496 KB |
testcase_07 | AC | 43 ms
56,640 KB |
testcase_08 | AC | 57 ms
66,044 KB |
testcase_09 | AC | 57 ms
66,888 KB |
testcase_10 | AC | 55 ms
66,440 KB |
testcase_11 | AC | 56 ms
67,044 KB |
testcase_12 | AC | 55 ms
66,572 KB |
testcase_13 | AC | 44 ms
57,316 KB |
testcase_14 | AC | 45 ms
57,492 KB |
testcase_15 | AC | 44 ms
55,992 KB |
testcase_16 | AC | 59 ms
69,452 KB |
testcase_17 | AC | 53 ms
65,972 KB |
testcase_18 | AC | 59 ms
68,260 KB |
testcase_19 | AC | 60 ms
68,908 KB |
testcase_20 | AC | 62 ms
69,344 KB |
testcase_21 | AC | 58 ms
69,524 KB |
testcase_22 | AC | 59 ms
68,616 KB |
testcase_23 | AC | 70 ms
71,636 KB |
testcase_24 | AC | 45 ms
57,112 KB |
testcase_25 | AC | 46 ms
57,556 KB |
testcase_26 | AC | 57 ms
66,572 KB |
testcase_27 | AC | 47 ms
57,860 KB |
testcase_28 | AC | 44 ms
57,724 KB |
testcase_29 | AC | 45 ms
56,352 KB |
testcase_30 | AC | 46 ms
56,368 KB |
testcase_31 | AC | 43 ms
56,124 KB |
testcase_32 | AC | 45 ms
56,880 KB |
testcase_33 | AC | 42 ms
55,808 KB |
testcase_34 | AC | 886 ms
296,812 KB |
testcase_35 | AC | 42 ms
55,716 KB |
testcase_36 | AC | 42 ms
55,224 KB |
testcase_37 | AC | 40 ms
55,324 KB |
testcase_38 | AC | 41 ms
55,576 KB |
testcase_39 | AC | 40 ms
55,864 KB |
testcase_40 | AC | 1,089 ms
296,296 KB |
testcase_41 | AC | 1,091 ms
297,200 KB |
testcase_42 | AC | 715 ms
233,448 KB |
testcase_43 | AC | 885 ms
277,512 KB |
testcase_44 | AC | 1,095 ms
314,264 KB |
testcase_45 | AC | 823 ms
184,708 KB |
testcase_46 | AC | 739 ms
168,436 KB |
testcase_47 | AC | 513 ms
117,224 KB |
testcase_48 | AC | 511 ms
119,176 KB |
testcase_49 | AC | 521 ms
123,688 KB |
testcase_50 | AC | 356 ms
121,408 KB |
testcase_51 | AC | 750 ms
252,064 KB |
testcase_52 | AC | 1,023 ms
311,848 KB |
testcase_53 | AC | 1,055 ms
320,568 KB |
testcase_54 | AC | 672 ms
224,404 KB |
testcase_55 | AC | 678 ms
247,600 KB |
testcase_56 | AC | 616 ms
239,624 KB |
testcase_57 | AC | 637 ms
250,752 KB |
testcase_58 | AC | 710 ms
263,316 KB |
testcase_59 | AC | 664 ms
249,124 KB |
testcase_60 | AC | 653 ms
261,860 KB |
testcase_61 | AC | 666 ms
256,440 KB |
testcase_62 | AC | 760 ms
263,132 KB |
testcase_63 | AC | 686 ms
252,176 KB |
testcase_64 | AC | 620 ms
244,000 KB |
testcase_65 | AC | 401 ms
158,256 KB |
testcase_66 | AC | 426 ms
165,944 KB |
testcase_67 | AC | 454 ms
169,444 KB |
testcase_68 | AC | 731 ms
253,076 KB |
testcase_69 | AC | 538 ms
193,228 KB |
testcase_70 | AC | 689 ms
249,908 KB |
testcase_71 | AC | 345 ms
143,772 KB |
testcase_72 | AC | 516 ms
192,680 KB |
testcase_73 | AC | 738 ms
251,716 KB |
testcase_74 | AC | 709 ms
247,816 KB |
testcase_75 | AC | 224 ms
119,956 KB |
testcase_76 | AC | 189 ms
109,220 KB |
testcase_77 | AC | 441 ms
180,100 KB |
testcase_78 | AC | 514 ms
199,304 KB |
testcase_79 | AC | 253 ms
104,328 KB |
testcase_80 | AC | 281 ms
103,116 KB |
testcase_81 | AC | 442 ms
130,508 KB |
testcase_82 | AC | 398 ms
136,416 KB |
testcase_83 | AC | 256 ms
138,016 KB |
61_evil_bias_nocross_01.txt | AC | 1,094 ms
305,624 KB |
61_evil_bias_nocross_02.txt | AC | 1,094 ms
312,020 KB |
61_evil_bias_nocross_03.txt | AC | 687 ms
240,236 KB |
61_evil_bias_nocross_04.txt | AC | 923 ms
279,348 KB |
61_evil_bias_nocross_05.txt | AC | 1,040 ms
309,764 KB |
61_evil_bias_nocross_06.txt | AC | 1,088 ms
300,664 KB |
61_evil_bias_nocross_07.txt | AC | 729 ms
252,696 KB |
61_evil_bias_nocross_08.txt | AC | 1,003 ms
310,168 KB |
61_evil_bias_nocross_09.txt | AC | 1,045 ms
285,228 KB |
61_evil_bias_nocross_10.txt | AC | 633 ms
225,804 KB |
61_evil_bias_nocross_11.txt | AC | 825 ms
274,356 KB |
61_evil_bias_nocross_12.txt | AC | 1,001 ms
297,696 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) Z[i].append((0,-1,-1)) 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][W[i+1][3]]][0]==0): dp[i+1][jjj]+=dp[i][j] ANS+=sum(dp[-1]) print(ANS)