結果
問題 | No.1640 簡単な色塗り |
ユーザー | kyaneko999 |
提出日時 | 2021-08-06 21:57:35 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 1,482 ms / 2,000 ms |
コード長 | 4,895 bytes |
コンパイル時間 | 517 ms |
コンパイル使用メモリ | 87,400 KB |
実行使用メモリ | 149,668 KB |
最終ジャッジ日時 | 2023-09-12 01:56:15 |
合計ジャッジ時間 | 54,962 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 148 ms
85,056 KB |
testcase_01 | AC | 147 ms
85,168 KB |
testcase_02 | AC | 148 ms
77,808 KB |
testcase_03 | AC | 148 ms
77,936 KB |
testcase_04 | AC | 338 ms
144,304 KB |
testcase_05 | AC | 952 ms
145,448 KB |
testcase_06 | AC | 148 ms
77,844 KB |
testcase_07 | AC | 147 ms
77,812 KB |
testcase_08 | AC | 147 ms
78,048 KB |
testcase_09 | AC | 149 ms
77,952 KB |
testcase_10 | AC | 1,008 ms
119,588 KB |
testcase_11 | AC | 867 ms
111,736 KB |
testcase_12 | AC | 829 ms
110,408 KB |
testcase_13 | AC | 1,449 ms
143,308 KB |
testcase_14 | AC | 1,482 ms
144,280 KB |
testcase_15 | AC | 687 ms
101,660 KB |
testcase_16 | AC | 733 ms
106,028 KB |
testcase_17 | AC | 1,227 ms
132,184 KB |
testcase_18 | AC | 348 ms
86,004 KB |
testcase_19 | AC | 832 ms
109,284 KB |
testcase_20 | AC | 980 ms
116,760 KB |
testcase_21 | AC | 868 ms
110,700 KB |
testcase_22 | AC | 315 ms
84,420 KB |
testcase_23 | AC | 1,057 ms
120,264 KB |
testcase_24 | AC | 517 ms
92,536 KB |
testcase_25 | AC | 826 ms
108,544 KB |
testcase_26 | AC | 1,107 ms
125,260 KB |
testcase_27 | AC | 654 ms
100,264 KB |
testcase_28 | AC | 1,437 ms
142,580 KB |
testcase_29 | AC | 1,160 ms
127,032 KB |
testcase_30 | AC | 438 ms
89,568 KB |
testcase_31 | AC | 1,377 ms
141,140 KB |
testcase_32 | AC | 1,251 ms
135,720 KB |
testcase_33 | AC | 910 ms
118,132 KB |
testcase_34 | AC | 1,095 ms
128,212 KB |
testcase_35 | AC | 916 ms
116,704 KB |
testcase_36 | AC | 442 ms
89,788 KB |
testcase_37 | AC | 530 ms
93,832 KB |
testcase_38 | AC | 1,261 ms
136,152 KB |
testcase_39 | AC | 696 ms
104,700 KB |
testcase_40 | AC | 698 ms
104,040 KB |
testcase_41 | AC | 1,097 ms
126,320 KB |
testcase_42 | AC | 766 ms
107,760 KB |
testcase_43 | AC | 807 ms
110,496 KB |
testcase_44 | AC | 759 ms
109,188 KB |
testcase_45 | AC | 672 ms
102,380 KB |
testcase_46 | AC | 449 ms
90,820 KB |
testcase_47 | AC | 395 ms
87,780 KB |
testcase_48 | AC | 1,326 ms
141,472 KB |
testcase_49 | AC | 331 ms
85,012 KB |
testcase_50 | AC | 146 ms
77,876 KB |
testcase_51 | AC | 149 ms
77,992 KB |
testcase_52 | AC | 1,409 ms
148,604 KB |
testcase_53 | AC | 1,444 ms
149,668 KB |
07_evil_01.txt | TLE | - |
07_evil_02.txt | TLE | - |
ソースコード
from sys import exit, stdin, setrecursionlimit from collections import deque, defaultdict, Counter from copy import deepcopy from bisect import bisect_left, bisect_right, insort_left, insort_right from heapq import heapify, heappop, heappush from itertools import product, permutations, combinations, combinations_with_replacement from functools import reduce from math import gcd, sin, cos, tan, asin, acos, atan, atan2, degrees, radians, ceil, floor, sqrt, factorial from math import pi as PI from random import randint as rd setrecursionlimit(500000) INF = (1<<61)-1 EPS = 1e-10 MOD = 10**9+7 # MOD = 998244353 def input(): return stdin.readline().strip('\n') def intput(): return int(input()) def minput(): return input().split() def linput(): return input().split() def mint(): return map(int,input().split()) def lint(): return list(map(int,input().split())) def ilint(): return intput(),lint() def lcm(x,y): return x*y//gcd(x,y) def lgcd(l): return reduce(gcd,l) def llcm(l): return reduce(lcm,l) def powmod(n,i,mod=MOD): return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod) def div2(x): return x.bit_length() def div10(x): return len(str(x))-(x==0) def popcount(x): return bin(x).count('1') def digit(x,i,max_len=None): s = str(x) if max_len: i -= max_len-len(s) return int(s[i-1]) if i>0 else 0 def digitsum(x): ans = 0 for i in range(div10(x)): ans += digit(x,i+1) return ans def pf(x,mode='counter'): C = Counter() p = 2 while x>1: k = 0 while x%p==0: x //= p k += 1 if k>0: C[p] += k p = p+2-(p==2) if p*p<x else x if mode=='counter': return C S = set([1]) for k in C: T = set() for x in S: for i in range(C[k]+1): T.add(x*(k**i)) S = T if mode=='set': return S if mode=='list': return sorted(S) def isprime(x): if x<2: return False return len(pf(x,'set'))==2 def matmul(A, B): # import numpy A1, A2 = A >> 15, A & (1 << 15) - 1 B1, B2 = B >> 15, B & (1 << 15) - 1 X = np.dot(A1, B1) % MOD Y = np.dot(A2, B2) Z = np.dot(A1 + A2, B1 + B2) - X - Y return ((X << 30) + (Z << 15) + Y) % MOD def matpow(A, N): P = np.eye(A.shape[0], dtype=np.int64) while N: if N & 1: P = matmul(P, A) A = matmul(A, A) N >>= 1 return P def zash(S): lis = sorted(S) dic = {} for i,x in enumerate(lis): dic[x] = i return lis, dic def pr(*x): print(*x, sep='', end='') if len(x) else print() def lprint(l): for x in l: print(x) def ston(c, c0='a'): return ord(c)-ord(c0) def ntos(x, c0='a'): return chr(x+ord(c0)) def judge(x, l=['Yes', 'No']): print(l[0] if x else l[1]) def debug(*x, flag=1): if flag: print(*x) ###################################################### class UnionFind(): # インデックスは0-start # 初期化 def __init__(self, n): self.n = n self.parents = [-1]*n self.group = n # private function def root(self, x): if self.parents[x]<0: return x else: self.parents[x] = self.root(self.parents[x]) return self.parents[x] # x,yが属するグループの結合 def union(self, x, y): x = self.root(x) y = self.root(y) if x==y: return if self.parents[x]>self.parents[y]: x,y = y,x self.parents[x] += self.parents[y] self.parents[y] = x self.group -= 1 # x,yが同グループか判定 def same(self, x, y): return self.root(x)==self.root(y) # xと同じグループの要素数を取得 def size(self, x): return -self.parents[self.root(x)] # xが親かを判定 def isparent(self, x): return self.parents[x]<0 N=intput() node=[set() for _ in range(N+1)] edge=[] cnt=[0]*(N+1) U=UnionFind(N+1) for i in range(N): a,b=mint() node[a].add(i) node[b].add(i) edge.append([a,b]) cnt[a]+=1 cnt[b]+=1 U.union(a,b) G=defaultdict(list) for x in range(1,N+1): r=U.root(x) G[r].append(x) ans=[-1]*N for l in G.values(): h=[] done=set() for x in l: heappush(h,[cnt[x],x]) while h: _,x=heappop(h) if x in done: continue if cnt[x]==0: judge(0) exit() i=node[x].pop() cnt[x]-=1 ans[i]=x done.add(x) for y in edge[i]: if x!=y: node[y].remove(i) cnt[y]-=1 if y not in done: heappush(h,[cnt[y],y]) if sorted(ans)==list(range(1,N+1)): judge(1) lprint(ans) else: judge(0)