結果

問題 No.1640 簡単な色塗り
ユーザー kyaneko999kyaneko999
提出日時 2021-08-06 21:52:32
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,783 bytes
コンパイル時間 809 ms
コンパイル使用メモリ 87,184 KB
実行使用メモリ 144,080 KB
最終ジャッジ日時 2023-09-12 01:49:31
合計ジャッジ時間 33,578 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 147 ms
78,152 KB
testcase_01 AC 145 ms
78,068 KB
testcase_02 AC 144 ms
78,076 KB
testcase_03 AC 145 ms
78,128 KB
testcase_04 AC 332 ms
144,080 KB
testcase_05 RE -
testcase_06 AC 143 ms
77,948 KB
testcase_07 AC 145 ms
77,852 KB
testcase_08 AC 144 ms
77,964 KB
testcase_09 AC 142 ms
78,112 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
07_evil_01.txt RE -
07_evil_02.txt RE -
権限があれば一括ダウンロードができます

ソースコード

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=0):
    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():
    debug(l)
    debug(node)
    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()
        ans[i]=x
        for y in edge[i]:
            if x!=y:
                node[y].remove(i)
if sorted(ans)==list(range(1,N+1)):
    judge(1)
    lprint(ans)
else:
    judge(0)
0