結果

問題 No.1420 国勢調査 (Easy)
コンテスト
ユーザー googol_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

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