提出 #6389754


ソースコード 拡げる

Copy
#import resource
import sys
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
import threading
threading.stack_size(2**25)
sys.setrecursionlimit(10**6)
mod=(10**9)+7
fact=[1]
#for i in range(1,1001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*1001
#ifact[1000]=pow(fact[1000],mod-2,mod)
#for i in range(1000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import math
import heapq
#from random import randint as rn
from Queue import Queue as Q
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def GCD(x, y):
   while(y):
       x, y = y, x % y
   return x
def isprime(x):
    p=int(math.sqrt(x))+1
    if(x==1):
        return 0
    for i in range(2,p):
        if(x%p==0):
            return 0
    return 1
"""**************************************************************************"""
def main():
    def find(x):
        if(p[x]!=x):
            x=find(p[x])
        return p[x]
    def union(u,v):
        a=find(u)
        b=find(v)
        if(r[a]>r[b]):
            p[b]=a
        elif(r[a]<r[b]):
            p[a]=b
        else:
            p[b]=a
            r[a]+=1
    def dfs(x,y):
        if(p[x]==0):
            p[x]=1
            for i in b1[x]:
                dfs(i,x)
            if(x!=0):
                if(deg[x]%2!=0):
                    t=1
                    deg[x]+=1
                else:
                    t=0
                    deg[y]+=1
                if(c.has_key((x,y))==True):
                    if(t==1):
                        ans[c[(x,y)]]=1
                else:
                    if(t==0):
                        ans[c[(y,x)]]=1
    for _ in range(1):
        n,m=ain()
        b=[]
        r=[0]*n
        p=[i for i in range(n)]
        for i in range(m):
            x,y=ain()
            b.append((x-1,y-1))
        q=n-1
        c={}
        b1=[[] for i in range(n)]
        i=0
        while(q>0):
            g=find(b[i][0])
            h=find(b[i][1])
            if(g!=h):
                q-=1
                c[b[i]]=i
                b1[b[i][0]].append(b[i][1])
                b1[b[i][1]].append(b[i][0])
                union(b[i][0],b[i][1])
            i+=1
        deg=[0]*n
        ans=[0]*m
        for i in range(m):
            if(c.has_key(b[i])==False):
                deg[b[i][1]]+=1
        p=[0]*n
        dfs(0,-1)
        if(deg[0]%2==1):
            print -1
            continue
        else:
            for i in range(m):
                print ans[i],
            print
threading.Thread(target=main).start()

提出情報

提出日時
問題 A - XOR Circle
ユーザ priyam2k
言語 PyPy2 (5.6.0)
得点 0
コード長 2915 Byte
結果 WA
実行時間 63 ms
メモリ 32872 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 300
結果
WA × 2
WA × 22
セット名 テストケース
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt
ケース名 結果 実行時間 メモリ
sample_01.txt WA 63 ms 31720 KB
sample_02.txt WA 38 ms 30952 KB
test_01.txt WA 39 ms 30312 KB
test_02.txt WA 39 ms 30440 KB
test_03.txt WA 38 ms 29544 KB
test_04.txt WA 39 ms 30056 KB
test_05.txt WA 39 ms 30312 KB
test_06.txt WA 38 ms 31080 KB
test_07.txt WA 39 ms 31336 KB
test_08.txt WA 38 ms 29672 KB
test_09.txt WA 38 ms 29672 KB
test_10.txt WA 39 ms 31336 KB
test_11.txt WA 38 ms 29544 KB
test_12.txt WA 39 ms 32872 KB
test_13.txt WA 39 ms 30312 KB
test_14.txt WA 38 ms 29544 KB
test_15.txt WA 39 ms 30056 KB
test_16.txt WA 39 ms 30568 KB
test_17.txt WA 38 ms 31208 KB
test_18.txt WA 38 ms 29544 KB
test_19.txt WA 39 ms 31208 KB
test_20.txt WA 39 ms 29544 KB