Submission #2708406


Source Code Expand

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):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])
    R = []
    for j in G[i]:
        R.append(Q[j])

    if R:
        R.sort(key=len, reverse=1)

        last = R.pop()
        while R:
            nxt = R.pop()
            for k in range(len(nxt)):
                if last:
                    a0, a1, a2, c0 = last.popleft()
                    b0, b1, b2, c1 = nxt.popleft()
                    C = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
                    nxt.append(C)
                else:
                    nxt.append(nxt.popleft())
            last = nxt
        # a0 <- a2
        for e in last:
            e[0] += e[2]
            e[2] = 0
        q.extend(last)
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 1093 Byte
Status TLE
Exec Time 3171 ms
Memory 245564 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 20 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 24 ms 3828 KB
s1_02.txt AC 24 ms 3828 KB
s1_03.txt AC 26 ms 4340 KB
s1_04.txt AC 21 ms 3316 KB
s1_05.txt AC 23 ms 3700 KB
s1_06.txt AC 28 ms 4980 KB
s1_07.txt AC 23 ms 3700 KB
s1_08.txt AC 385 ms 21236 KB
s1_09.txt AC 46 ms 4852 KB
s1_10.txt AC 30 ms 5108 KB
s1_11.txt AC 23 ms 3700 KB
s1_12.txt AC 26 ms 4340 KB
s1_13.txt AC 21 ms 3316 KB
s1_14.txt AC 31 ms 4980 KB
s1_15.txt AC 32 ms 5108 KB
s1_16.txt AC 30 ms 4980 KB
s1_17.txt AC 31 ms 5108 KB
s2_01.txt AC 115 ms 18124 KB
s2_02.txt AC 40 ms 6260 KB
s2_03.txt AC 818 ms 115560 KB
s2_04.txt AC 533 ms 71628 KB
s2_05.txt AC 1107 ms 125276 KB
s2_06.txt AC 1269 ms 166176 KB
s2_07.txt AC 854 ms 103948 KB
s2_08.txt AC 399 ms 54664 KB
s2_09.txt AC 1259 ms 162708 KB
s2_10.txt AC 1083 ms 126248 KB
s2_11.txt AC 985 ms 178000 KB
s2_12.txt AC 32 ms 6132 KB
s2_13.txt TLE 3165 ms 163840 KB
s2_14.txt TLE 3167 ms 188988 KB
s2_15.txt TLE 3165 ms 156180 KB
s2_16.txt AC 104 ms 18652 KB
s2_17.txt AC 37 ms 6260 KB
s2_18.txt AC 811 ms 120300 KB
s2_19.txt AC 463 ms 73572 KB
s2_20.txt AC 1706 ms 181096 KB
s2_21.txt AC 1835 ms 188432 KB
s2_22.txt AC 1386 ms 178580 KB
s2_23.txt AC 1680 ms 180940 KB
s2_24.txt AC 2316 ms 217016 KB
s2_25.txt TLE 3171 ms 245564 KB
s2_26.txt TLE 3168 ms 217148 KB
s2_27.txt TLE 3164 ms 160200 KB
s2_28.txt TLE 3167 ms 186236 KB
s2_29.txt TLE 3167 ms 193876 KB
s2_30.txt TLE 3167 ms 193148 KB
s2_31.txt TLE 3167 ms 192828 KB
s2_32.txt TLE 3167 ms 191932 KB