Submission #2708433


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 Python (3.4.3)
Score 400
Code Size 1115 Byte
Status TLE
Exec Time 3162 ms
Memory 174804 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 600
Status
AC × 3
AC × 20
AC × 41
TLE × 11
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 21 ms 3316 KB
00_example_02.txt AC 21 ms 3316 KB
00_example_03.txt AC 21 ms 3316 KB
s1_01.txt AC 23 ms 3700 KB
s1_02.txt AC 23 ms 3572 KB
s1_03.txt AC 25 ms 4212 KB
s1_04.txt AC 21 ms 3316 KB
s1_05.txt AC 22 ms 3572 KB
s1_06.txt AC 28 ms 4980 KB
s1_07.txt AC 23 ms 3700 KB
s1_08.txt AC 390 ms 3832 KB
s1_09.txt AC 41 ms 3444 KB
s1_10.txt AC 27 ms 4596 KB
s1_11.txt AC 22 ms 3572 KB
s1_12.txt AC 24 ms 4080 KB
s1_13.txt AC 21 ms 3316 KB
s1_14.txt AC 27 ms 4596 KB
s1_15.txt AC 28 ms 4468 KB
s1_16.txt AC 29 ms 4724 KB
s1_17.txt AC 28 ms 4596 KB
s2_01.txt AC 83 ms 14296 KB
s2_02.txt AC 32 ms 5236 KB
s2_03.txt AC 662 ms 97016 KB
s2_04.txt AC 402 ms 53952 KB
s2_05.txt AC 704 ms 82880 KB
s2_06.txt AC 1051 ms 139164 KB
s2_07.txt AC 616 ms 77912 KB
s2_08.txt AC 272 ms 36848 KB
s2_09.txt AC 1031 ms 136392 KB
s2_10.txt AC 722 ms 94400 KB
s2_11.txt AC 964 ms 174804 KB
s2_12.txt AC 31 ms 6004 KB
s2_13.txt TLE 3158 ms 43516 KB
s2_14.txt TLE 3158 ms 43332 KB
s2_15.txt TLE 3158 ms 39444 KB
s2_16.txt AC 82 ms 14416 KB
s2_17.txt AC 31 ms 5364 KB
s2_18.txt AC 545 ms 88232 KB
s2_19.txt AC 325 ms 54328 KB
s2_20.txt AC 1161 ms 134856 KB
s2_21.txt AC 1169 ms 124224 KB
s2_22.txt AC 1109 ms 149636 KB
s2_23.txt AC 1173 ms 134840 KB
s2_24.txt AC 1212 ms 93852 KB
s2_25.txt TLE 3160 ms 72228 KB
s2_26.txt TLE 3159 ms 51300 KB
s2_27.txt TLE 3158 ms 43392 KB
s2_28.txt TLE 3158 ms 43520 KB
s2_29.txt TLE 3158 ms 47620 KB
s2_30.txt TLE 3162 ms 47612 KB
s2_31.txt TLE 3158 ms 47940 KB
s2_32.txt TLE 3158 ms 47932 KB