結果

問題 No.2160 みたりのDominator
ユーザー googol_S0googol_S0
提出日時 2022-12-11 03:16:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,151 ms / 2,000 ms
コード長 5,899 bytes
コンパイル時間 1,028 ms
コンパイル使用メモリ 87,208 KB
実行使用メモリ 324,024 KB
最終ジャッジ日時 2023-09-07 04:20:20
合計ジャッジ時間 56,454 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,404 KB
testcase_01 AC 1,026 ms
306,924 KB
testcase_02 AC 75 ms
71,396 KB
testcase_03 AC 76 ms
71,172 KB
testcase_04 AC 78 ms
71,396 KB
testcase_05 AC 78 ms
71,404 KB
testcase_06 AC 77 ms
71,224 KB
testcase_07 AC 78 ms
71,044 KB
testcase_08 AC 89 ms
76,672 KB
testcase_09 AC 89 ms
76,828 KB
testcase_10 AC 87 ms
76,804 KB
testcase_11 AC 90 ms
76,628 KB
testcase_12 AC 89 ms
76,488 KB
testcase_13 AC 81 ms
71,208 KB
testcase_14 AC 77 ms
71,424 KB
testcase_15 AC 74 ms
71,220 KB
testcase_16 AC 90 ms
76,672 KB
testcase_17 AC 87 ms
76,496 KB
testcase_18 AC 92 ms
76,584 KB
testcase_19 AC 94 ms
76,568 KB
testcase_20 AC 94 ms
76,748 KB
testcase_21 AC 91 ms
76,520 KB
testcase_22 AC 92 ms
76,724 KB
testcase_23 AC 102 ms
76,288 KB
testcase_24 AC 80 ms
71,540 KB
testcase_25 AC 81 ms
71,352 KB
testcase_26 AC 89 ms
76,276 KB
testcase_27 AC 80 ms
71,368 KB
testcase_28 AC 77 ms
71,520 KB
testcase_29 AC 77 ms
71,176 KB
testcase_30 AC 76 ms
71,296 KB
testcase_31 AC 78 ms
71,168 KB
testcase_32 AC 78 ms
71,416 KB
testcase_33 AC 73 ms
71,168 KB
testcase_34 AC 928 ms
298,600 KB
testcase_35 AC 74 ms
71,204 KB
testcase_36 AC 75 ms
71,092 KB
testcase_37 AC 74 ms
71,208 KB
testcase_38 AC 74 ms
71,384 KB
testcase_39 AC 75 ms
71,280 KB
testcase_40 AC 1,116 ms
305,968 KB
testcase_41 AC 1,151 ms
307,724 KB
testcase_42 AC 751 ms
233,992 KB
testcase_43 AC 927 ms
277,308 KB
testcase_44 AC 1,133 ms
324,024 KB
testcase_45 AC 891 ms
186,556 KB
testcase_46 AC 789 ms
169,628 KB
testcase_47 AC 571 ms
123,048 KB
testcase_48 AC 570 ms
122,972 KB
testcase_49 AC 540 ms
122,884 KB
testcase_50 AC 401 ms
122,448 KB
testcase_51 AC 790 ms
254,116 KB
testcase_52 AC 1,054 ms
312,852 KB
testcase_53 AC 1,110 ms
317,720 KB
testcase_54 AC 736 ms
226,716 KB
testcase_55 AC 762 ms
252,308 KB
testcase_56 AC 684 ms
243,328 KB
testcase_57 AC 703 ms
256,264 KB
testcase_58 AC 780 ms
265,404 KB
testcase_59 AC 734 ms
252,196 KB
testcase_60 AC 699 ms
263,572 KB
testcase_61 AC 724 ms
248,828 KB
testcase_62 AC 816 ms
267,848 KB
testcase_63 AC 752 ms
253,292 KB
testcase_64 AC 684 ms
251,896 KB
testcase_65 AC 455 ms
160,572 KB
testcase_66 AC 489 ms
167,464 KB
testcase_67 AC 493 ms
160,384 KB
testcase_68 AC 788 ms
244,576 KB
testcase_69 AC 606 ms
200,424 KB
testcase_70 AC 753 ms
246,872 KB
testcase_71 AC 400 ms
145,676 KB
testcase_72 AC 583 ms
198,884 KB
testcase_73 AC 800 ms
251,956 KB
testcase_74 AC 783 ms
241,664 KB
testcase_75 AC 268 ms
123,096 KB
testcase_76 AC 224 ms
111,592 KB
testcase_77 AC 499 ms
182,804 KB
testcase_78 AC 576 ms
186,872 KB
testcase_79 AC 298 ms
98,484 KB
testcase_80 AC 336 ms
106,756 KB
testcase_81 AC 513 ms
134,300 KB
testcase_82 AC 449 ms
132,288 KB
testcase_83 AC 286 ms
125,540 KB
61_evil_bias_nocross_01.txt AC 1,135 ms
329,044 KB
61_evil_bias_nocross_02.txt AC 1,155 ms
312,248 KB
61_evil_bias_nocross_03.txt AC 747 ms
241,856 KB
61_evil_bias_nocross_04.txt AC 912 ms
282,804 KB
61_evil_bias_nocross_05.txt AC 1,091 ms
309,832 KB
61_evil_bias_nocross_06.txt AC 1,179 ms
315,660 KB
61_evil_bias_nocross_07.txt AC 798 ms
254,080 KB
61_evil_bias_nocross_08.txt AC 1,050 ms
311,016 KB
61_evil_bias_nocross_09.txt AC 1,092 ms
285,720 KB
61_evil_bias_nocross_10.txt AC 694 ms
225,592 KB
61_evil_bias_nocross_11.txt AC 876 ms
274,416 KB
61_evil_bias_nocross_12.txt AC 1,022 ms
298,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0