結果

問題 No.1420 国勢調査 (Easy)
ユーザー googol_S0googol_S0
提出日時 2021-03-05 21:39:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,267 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 406,592 KB
最終ジャッジ日時 2024-10-07 01:04:03
合計ジャッジ時間 4,569 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
58,752 KB
testcase_01 AC 40 ms
52,992 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(len(G)):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

N,M=map(int,input().split())
G=[[] for i in range(N*60)]
for t in range(M):
  A,B=map(int,input().split())
  Y=int(input())
  A-=1
  B-=1
  for i in range(30):
    X=(Y&(1<<i))>>i
    for j in range(2):
      for k in range(2):
        if j^k^X:
          G[A*30+i+j*N*30].append(B*30+i+(1^k)*N*30)
          G[B*30+i+k*N*30].append(A*30+i+(1^j)*N*30)
G=SCC(G)
C=[0]*(60*N)
for i in range(len(G)):
  for j in range(len(G[i])):
    C[G[i][j]]=i
for i in range(N*30):
  if C[i]==C[i+N*30]:
    print(-1)
    exit()
for i in range(N):
  x=0
  for j in range(30):
    if C[i*30+j]<=C[i*30+j+N*30]:
      x+=1<<j
  print(x)
0