結果

問題 No.1640 簡単な色塗り
ユーザー kyaneko999kyaneko999
提出日時 2021-08-06 21:57:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,178 ms / 2,000 ms
コード長 4,895 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 146,440 KB
最終ジャッジ日時 2024-06-29 15:07:09
合計ジャッジ時間 42,422 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
72,612 KB
testcase_01 AC 51 ms
66,352 KB
testcase_02 AC 53 ms
65,556 KB
testcase_03 AC 50 ms
65,268 KB
testcase_04 AC 220 ms
142,740 KB
testcase_05 AC 759 ms
144,224 KB
testcase_06 AC 50 ms
66,572 KB
testcase_07 AC 54 ms
66,208 KB
testcase_08 AC 55 ms
65,464 KB
testcase_09 AC 49 ms
66,472 KB
testcase_10 AC 750 ms
117,236 KB
testcase_11 AC 666 ms
109,232 KB
testcase_12 AC 590 ms
107,608 KB
testcase_13 AC 1,100 ms
141,704 KB
testcase_14 AC 1,110 ms
142,496 KB
testcase_15 AC 464 ms
98,072 KB
testcase_16 AC 527 ms
103,748 KB
testcase_17 AC 929 ms
129,796 KB
testcase_18 AC 212 ms
83,308 KB
testcase_19 AC 598 ms
106,276 KB
testcase_20 AC 717 ms
113,204 KB
testcase_21 AC 648 ms
108,432 KB
testcase_22 AC 202 ms
82,364 KB
testcase_23 AC 818 ms
118,600 KB
testcase_24 AC 352 ms
89,948 KB
testcase_25 AC 581 ms
105,900 KB
testcase_26 AC 961 ms
122,748 KB
testcase_27 AC 455 ms
97,904 KB
testcase_28 AC 1,120 ms
140,932 KB
testcase_29 AC 896 ms
123,760 KB
testcase_30 AC 280 ms
86,848 KB
testcase_31 AC 1,074 ms
140,284 KB
testcase_32 AC 968 ms
133,388 KB
testcase_33 AC 671 ms
115,256 KB
testcase_34 AC 833 ms
124,604 KB
testcase_35 AC 687 ms
113,768 KB
testcase_36 AC 290 ms
87,960 KB
testcase_37 AC 354 ms
91,640 KB
testcase_38 AC 967 ms
133,916 KB
testcase_39 AC 492 ms
101,656 KB
testcase_40 AC 487 ms
101,676 KB
testcase_41 AC 819 ms
123,292 KB
testcase_42 AC 582 ms
104,072 KB
testcase_43 AC 610 ms
108,300 KB
testcase_44 AC 545 ms
105,184 KB
testcase_45 AC 491 ms
100,536 KB
testcase_46 AC 294 ms
88,412 KB
testcase_47 AC 249 ms
85,644 KB
testcase_48 AC 1,029 ms
138,692 KB
testcase_49 AC 196 ms
82,500 KB
testcase_50 AC 50 ms
65,328 KB
testcase_51 AC 50 ms
66,364 KB
testcase_52 AC 1,131 ms
146,144 KB
testcase_53 AC 1,178 ms
146,440 KB
07_evil_01.txt TLE -
07_evil_02.txt TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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