#680568 (PyPy3) No.1612 I hate Construct a Palindrome

提出ソース

結果

問題	No.1612 I hate Construct a Palindrome
ユーザー	chineristAC
提出日時	2021-07-21 22:52:34
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	15,503 bytes
コンパイル時間	191 ms
コンパイル使用メモリ	82,388 KB
実行使用メモリ	153,900 KB
最終ジャッジ日時	2024-07-17 19:57:51
合計ジャッジ時間	9,283 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	48 ms 61,264 KB
testcase_01	AC	80 ms 78,408 KB
testcase_02	AC	431 ms 152,816 KB
testcase_03	AC	46 ms 60,556 KB
testcase_04	AC	76 ms 78,076 KB
testcase_05	AC	414 ms 153,900 KB
testcase_06	AC	386 ms 128,684 KB
testcase_07	AC	323 ms 122,500 KB
testcase_08	AC	401 ms 132,796 KB
testcase_09	AC	305 ms 113,028 KB
testcase_10	AC	308 ms 112,920 KB
testcase_11	AC	306 ms 112,964 KB
testcase_12	AC	338 ms 121,640 KB
testcase_13	AC	347 ms 121,420 KB
testcase_14	AC	335 ms 120,788 KB
testcase_15	AC	569 ms 149,136 KB
testcase_16	AC	560 ms 148,152 KB
testcase_17	AC	553 ms 149,040 KB
testcase_18	AC	57 ms 70,564 KB
testcase_19	AC	55 ms 71,016 KB
testcase_20	AC	57 ms 69,832 KB
testcase_21	AC	62 ms 73,500 KB
testcase_22	AC	62 ms 73,932 KB
testcase_23	AC	62 ms 72,888 KB
testcase_24	AC	64 ms 73,852 KB
testcase_25	AC	62 ms 73,896 KB
testcase_26	AC	60 ms 73,644 KB
testcase_27	AC	45 ms 61,612 KB
testcase_28	AC	46 ms 60,504 KB
testcase_29	AC	45 ms 61,844 KB
testcase_30	AC	45 ms 61,164 KB
testcase_31	AC	48 ms 60,448 KB
testcase_32	WA	-
testcase_33	AC	46 ms 60,832 KB
testcase_34	AC	47 ms 61,676 KB
testcase_35	AC	46 ms 62,388 KB
testcase_36	AC	50 ms 61,196 KB
testcase_37	AC	47 ms 60,976 KB
testcase_38	AC	46 ms 61,500 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

def divisors(M):
    d=[]
    i=1
    while M>=i**2:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    return d

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def eratosthenes(n):
    res=[0 for i in range(n+1)]
    prime=set([])
    for i in range(2,n+1):
        if not res[i]:
            prime.add(i)
            for j in range(1,n//i+1):
                res[i*j]=1
    return prime

def factorization(n):
    res=[]
    for p in prime:
        if n%p==0:
            while n%p==0:
                n//=p
            res.append(p)
    if n!=1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2,n+1):
        if x ** 2 > n:
            break
        if n%x==0:
            res = res//x * (x-1)
            while n%x==0:
                n //= x
    if n!=1:
        res = res//n * (n-1)
    return res

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p]+1):
                newres.append(d*p**j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):#排他的論理和の階乗
    if num==0:
        return 0
    elif num==1:
        return 1
    elif num==2:
        return 3
    elif num==3:
        return 0
    else:
        x=baseorder(num)
        return (2**x)*((num-2**x+1)%2)+function(num-2**x)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

def merge_sort(A,B):
    pos_A,pos_B = 0,0
    n,m = len(A),len(B)
    res = []
    while pos_A < n and pos_B < m:
        a,b = A[pos_A],B[pos_B]
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]]!=stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        self.group -= 1

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class WeightedUnionFind():
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.val = [0 for i in range(N)]
        self.flag = True
        self.edge = [[] for i in range(N)]

    def dfs(self,v,pv):
        stack = [(v,pv)]
        new_parent = self.parent[pv]
        while stack:
            v,pv = stack.pop()
            self.parent[v] = new_parent
            for nv,w in self.edge[v]:
                if nv!=pv:
                    self.val[nv] = self.val[v] + w
                    stack.append((nv,v))

    def unite(self,x,y,w):
        if not self.flag:
            return
        if self.parent[x]==self.parent[y]:
            self.flag = (self.val[x] - self.val[y] == w)
            return

        if self.size[self.parent[x]]>self.size[self.parent[y]]:
            self.edge[x].append((y,-w))
            self.edge[y].append((x,w))
            self.size[x] += self.size[y]
            self.val[y] = self.val[x] - w
            self.dfs(y,x)
        else:
            self.edge[x].append((y,-w))
            self.edge[y].append((x,w))
            self.size[y] += self.size[x]
            self.val[x] = self.val[y] + w
            self.dfs(x,y)

class Dijkstra():
    class Edge():
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add_edge(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

class BIT():
    def __init__(self,n,mod=0):
        self.BIT = [0]*(n+1)
        self.num = n
        self.mod = mod

    def query(self,idx):
        res_sum = 0
        mod = self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            if mod:
                res_sum %= mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod = self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            if mod:
                self.BIT[idx] %= mod
            idx += idx&(-idx)
        return

class dancinglink():
    def __init__(self,n,debug=False):
        self.n = n
        self.debug = debug
        self._left = [i-1 for i in range(n)]
        self._right = [i+1 for i in range(n)]
        self.exist = [True for i in range(n)]

    def pop(self,k):
        if self.debug:
            assert self.exist[k]
        L = self._left[k]
        R = self._right[k]
        if L!=-1:
            if R!=self.n:
                self._right[L],self._left[R] = R,L
            else:
                self._right[L] = self.n
        elif R!=self.n:
            self._left[R] = -1
        self.exist[k] = False

    def left(self,idx,k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._left[res]
            if res==-1:
                break
            k -= 1
        return res

    def right(self,idx,k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._right[res]
            if res==self.n:
                break
            k -= 1
        return res

class SparseTable():
    def __init__(self,A,merge_func,ide_ele):
        N=len(A)
        n=N.bit_length()
        self.table=[[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func=merge_func

        for i in range(N):
            self.table[i][0]=A[i]

        for j in range(1,n):
            for i in range(0,N-2**j+1):
                f=self.table[i][j-1]
                s=self.table[i+2**(j-1)][j-1]
                self.table[i][j]=self.merge_func(f,s)

    def query(self,s,t):
        b=t-s+1
        m=b.bit_length()-1
        return self.merge_func(self.table[s][m],self.table[t-2**m+1][m])

class BinaryTrie:
    class node:
        def __init__(self,val):
            self.left = None
            self.right = None
            self.max = val

    def __init__(self):
        self.root = self.node(-10**15)

    def append(self,key,val):
        pos = self.root
        for i in range(29,-1,-1):
            pos.max = max(pos.max,val)
            if key>>i & 1:
                if pos.right is None:
                    pos.right = self.node(val)
                    pos = pos.right
                else:
                    pos = pos.right
            else:
                if pos.left is None:
                    pos.left = self.node(val)
                    pos = pos.left
                else:
                    pos = pos.left
        pos.max = max(pos.max,val)

    def search(self,M,xor):
        res = -10**15
        pos = self.root
        for i in range(29,-1,-1):
            if pos is None:
                break

            if M>>i & 1:
                if xor>>i & 1:
                    if pos.right:
                        res = max(res,pos.right.max)
                    pos = pos.left
                else:
                    if pos.left:
                        res = max(res,pos.left.max)
                    pos = pos.right
            else:
                if xor>>i & 1:
                    pos = pos.right
                else:
                    pos = pos.left

        if pos:
            res = max(res,pos.max)
        return res

def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n
    for v in range(n):
        if used[v]:
            continue
        y = dfs(v)
        if y!=0:
            return False
    return x

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

class slope_trick():
    def __init__(self):
        self.L = [10**17]
        self.R = [10**17]
        self.min_f = 0

        self.x_move = 0

    def move(self,a):
        self.x_move += a

    def add_right(self,a):
        a -= self.x_move
        l0 = -self.L[0]
        if l0 <= a:
            heappush(self.R,a)
        else:
            heappush(self.L,-a)
            heappush(self.R,-heappop(self.L))

        self.min_f  = self.min_f + max(0,l0-a)

    def add_left(self,a):
        a -= self.x_move
        r0 = self.R[0]

        if a <= r0:
            heappush(self.L,-a)
        else:
            heappush(self.R,a)
            heappush(self.L,-heappop(self.R))

        self.min_f = self.min_f + max(0,a-r0)

    def add_abs(self,a):
        self.add_left(a)
        self.add_right(a)

    def change_min_left(self):
        self.R = [10**17]

    def change_min_right(self):
        self.L = [10**17]


import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

N,M = mi()
edge = [[] for v in range(N)]
al = ""
flag = True
for _ in range(M):
    a,b,c = input().split()
    a,b = int(a)-1,int(b)-1
    edge[a].append((b,c,_))
    edge[b].append((a,c,_))
    if al=="":
        al = c
    elif al!=c:
        flag = False

if flag:
    exit(print(-1))

back = [(-1,-1,-1) for v in range(N)]
back[0] = (-1,-2,-3)
deq = deque([0])
while deq:
    v = deq.popleft()
    for nv,c,idx in edge[v]:
        if back[nv]==(-1,-1,-1):
            back[nv] = (v,c,idx)
            deq.append(nv)

al = back[N-1][1]
flag = True
path = [N-1]
while path[-1]!=0:
    pv,c,idx = back[path[-1]]
    if c!=al:
        flag = False
    path.append(pv)

if not flag:
    ans = []
    for v in path:
        if v==0:
            break
        ans.append(back[v][2]+1)
    ans = ans[::-1]
    print(len(ans))
    print(*ans,sep="\n")
    exit()

S = set([v for v in path])
al_edge = [[] for v in range(N)]
for v in range(1,N):
    if back[v][1]==c:
        al_edge[back[v][0]].append(v)

deq = deque([0])
node = -1
while deq:
    v = deq.popleft()
    for nv,c,idx in edge[v]:
        if c!=al:
            node = (v,nv,idx)
            deq = []
            break
    else:
        for nv in al_edge[v]:
            deq.append(nv)

V,NV,IDX = node
path_for_diff = [NV,V]
while path_for_diff[-1] not in S:
    v = path_for_diff[-1]
    path_for_diff.append(back[v][0])

ans_1 = []
a = path_for_diff[-1]
while a!=0:
    ans_1.append(back[a][2])
    a = back[a][0]
ans_1 = ans_1[::-1]
ans_2 = []
a = V
while a!=path_for_diff[-1]:
    ans_2.append(back[a][2])
    a = back[a][0]
ans_2 = ans_2[::-1] + [IDX,IDX] + ans_2

ans_3 = []
a = N-1
while a!=path_for_diff[-1]:
    ans_3.append(back[a][2])
    a = back[a][0]
ans_3 = ans_3[::-1]

if len(ans_1)==len(ans_3):
    ans_3 += [back[N-1][2]] * 2

ans = ans_1 + ans_2 + ans_3
print(len(ans))
for e in ans:
    print(e+1)

yukicoder

結果

テストケース

ソースコード