Submission #2711445


Source Code Expand

# seishin.py
import sys
sys.setrecursionlimit(10**6)
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7
from itertools import tee

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
E = [1, 1, 0, 1]
def gen(i):
    *I, = map(Q.__getitem__, G[i])
    k = len(G[i])
    r = 1, k, pow(2, k, MOD) - k - 1, k
    while r:
        a,b,c,d=r
        yield (a+c,b,0,d)
        r = None
        for it in I:
            s = next(it, None)
            if s:
                if r:
                    a0, a1, a2, c0 = s
                    b0, b1, b2, c1 = r
                    r = a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, ((a0 + a1)*b2 + a1*b1) % MOD, c0+c1
                else:
                    r = s
*Q, = map(gen, range(N+1))
ans = pow(2, N, MOD)
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission Info

Submission Time
Task E - Smuggling Marbles
User yaketake08
Language PyPy3 (2.4.0)
Score 400
Code Size 914 Byte
Status TLE
Exec Time 3173 ms
Memory 288440 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 600
Status
AC × 3
AC × 20
AC × 38
TLE × 14
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 174 ms 38256 KB
00_example_02.txt AC 173 ms 38256 KB
00_example_03.txt AC 174 ms 38256 KB
s1_01.txt AC 220 ms 43628 KB
s1_02.txt AC 250 ms 46316 KB
s1_03.txt AC 216 ms 43504 KB
s1_04.txt AC 175 ms 38256 KB
s1_05.txt AC 200 ms 43504 KB
s1_06.txt AC 194 ms 42352 KB
s1_07.txt AC 176 ms 39408 KB
s1_08.txt AC 685 ms 121692 KB
s1_09.txt AC 238 ms 54700 KB
s1_10.txt AC 265 ms 50924 KB
s1_11.txt AC 177 ms 40432 KB
s1_12.txt AC 226 ms 46828 KB
s1_13.txt AC 168 ms 38256 KB
s1_14.txt AC 307 ms 53740 KB
s1_15.txt AC 372 ms 61272 KB
s1_16.txt AC 251 ms 47596 KB
s1_17.txt AC 269 ms 49004 KB
s2_01.txt AC 719 ms 104024 KB
s2_02.txt AC 385 ms 66396 KB
s2_03.txt AC 1684 ms 184072 KB
s2_04.txt AC 1501 ms 142908 KB
s2_05.txt AC 1732 ms 181920 KB
s2_06.txt AC 2388 ms 258284 KB
s2_07.txt AC 1859 ms 158992 KB
s2_08.txt AC 609 ms 132540 KB
s2_09.txt AC 2140 ms 235784 KB
s2_10.txt AC 2743 ms 190816 KB
s2_11.txt AC 568 ms 169032 KB
s2_12.txt AC 197 ms 43248 KB
s2_13.txt TLE 3173 ms 285624 KB
s2_14.txt TLE 3173 ms 285624 KB
s2_15.txt TLE 3172 ms 263980 KB
s2_16.txt AC 332 ms 71512 KB
s2_17.txt AC 292 ms 56920 KB
s2_18.txt AC 800 ms 218832 KB
s2_19.txt AC 596 ms 163020 KB
s2_20.txt AC 2988 ms 276524 KB
s2_21.txt TLE 3173 ms 279964 KB
s2_22.txt AC 2175 ms 240504 KB
s2_23.txt TLE 3172 ms 280240 KB
s2_24.txt TLE 3172 ms 273096 KB
s2_25.txt TLE 3172 ms 274744 KB
s2_26.txt TLE 3173 ms 288440 KB
s2_27.txt TLE 3173 ms 285496 KB
s2_28.txt TLE 3173 ms 285624 KB
s2_29.txt TLE 3173 ms 288440 KB
s2_30.txt TLE 3173 ms 288440 KB
s2_31.txt TLE 3172 ms 266552 KB
s2_32.txt TLE 3172 ms 266552 KB