Submission #2708431


Source Code Expand

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
for i in range(N, -1, -1):

    # 子ノードのdequeを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD
            r[3] = c0+c1
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        R.appendleft([1, 1, 0, 1])
        Q[i] = R
    else:
        Q[i] = deque([[1, 1, 0, 1]])
ans = 0
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 1117 Byte
Status TLE
Exec Time 3162 ms
Memory 184772 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 600
Status
AC × 3
AC × 20
AC × 43
TLE × 9
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 161 ms 38256 KB
00_example_02.txt AC 165 ms 38256 KB
00_example_03.txt AC 161 ms 38256 KB
s1_01.txt AC 164 ms 38256 KB
s1_02.txt AC 172 ms 39152 KB
s1_03.txt AC 186 ms 41200 KB
s1_04.txt AC 161 ms 38256 KB
s1_05.txt AC 170 ms 39024 KB
s1_06.txt AC 184 ms 42096 KB
s1_07.txt AC 164 ms 38384 KB
s1_08.txt AC 192 ms 40688 KB
s1_09.txt AC 171 ms 39280 KB
s1_10.txt AC 196 ms 42480 KB
s1_11.txt AC 163 ms 38256 KB
s1_12.txt AC 185 ms 41072 KB
s1_13.txt AC 162 ms 38256 KB
s1_14.txt AC 198 ms 42608 KB
s1_15.txt AC 204 ms 42480 KB
s1_16.txt AC 194 ms 42096 KB
s1_17.txt AC 203 ms 43376 KB
s2_01.txt AC 271 ms 55404 KB
s2_02.txt AC 219 ms 45036 KB
s2_03.txt AC 676 ms 123108 KB
s2_04.txt AC 460 ms 97660 KB
s2_05.txt AC 629 ms 131440 KB
s2_06.txt AC 915 ms 150892 KB
s2_07.txt AC 601 ms 125860 KB
s2_08.txt AC 371 ms 78268 KB
s2_09.txt AC 903 ms 143880 KB
s2_10.txt AC 734 ms 131536 KB
s2_11.txt AC 537 ms 184772 KB
s2_12.txt AC 185 ms 42992 KB
s2_13.txt TLE 3161 ms 106264 KB
s2_14.txt TLE 3161 ms 106264 KB
s2_15.txt TLE 3161 ms 98432 KB
s2_16.txt AC 223 ms 51568 KB
s2_17.txt AC 214 ms 45168 KB
s2_18.txt AC 374 ms 120840 KB
s2_19.txt AC 314 ms 88588 KB
s2_20.txt AC 890 ms 133672 KB
s2_21.txt AC 823 ms 125336 KB
s2_22.txt AC 943 ms 159860 KB
s2_23.txt AC 866 ms 131628 KB
s2_24.txt AC 553 ms 128408 KB
s2_25.txt AC 639 ms 137112 KB
s2_26.txt AC 1349 ms 126104 KB
s2_27.txt TLE 3162 ms 111384 KB
s2_28.txt TLE 3161 ms 110104 KB
s2_29.txt TLE 3161 ms 115768 KB
s2_30.txt TLE 3161 ms 114108 KB
s2_31.txt TLE 3161 ms 115260 KB
s2_32.txt TLE 3161 ms 114232 KB