Submission #3715959


Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <deque>
using namespace std;
using Graph = vector< vector<int> >;
using ll = long long int;

int cnt_depth[200010], pow2[200010];
const ll MOD = 1000000007;

struct Node {
    ll a, b, c;
    Node() {
        a = b = c = 0;
    }
    Node(ll x, ll y, ll z) : a(x), b(y), c(z) {}
};

Node merge(Node lhs, Node rhs) {
    Node res;
    res.a = (lhs.a * rhs.a) % MOD;
    res.b = ((lhs.a * rhs.b) % MOD + (lhs.b * rhs.a) % MOD) % MOD;
    res.c = 0;
    (res.c += lhs.c * (rhs.a + rhs.b + rhs.c)) %= MOD;
    (res.c += lhs.b * (rhs.b + rhs.c)) %= MOD;
    (res.c += lhs.a * rhs.c) %= MOD;
    return res;
}

deque<Node> solve(Graph &G, int cur, int depth=0) {
    cnt_depth[depth]++;
    deque<Node> res;

    int sz = 0;
    for(auto to : G[cur]) {
        auto nxt = solve(G, to, depth + 1);
        if(res.size() < nxt.size()) swap(res, nxt);

        for(size_t i=0; i<nxt.size(); i++) {
            res[i] = merge(res[i], nxt[i]);
        }
        sz = max<int>(sz, nxt.size());
    }

    for(int i=0; i<sz; i++) {
        (res[i].a += res[i].c) %= MOD;
        res[i].c = 0;
    }

    res.push_front(Node(1, 1, 0));
    return res;
}

int main() {
    ll N, ans = 0; cin >> N;

    Graph G(N+1);
    pow2[0] = 1, pow2[1] = 2;
    for(int i=1; i<=N; i++) {
        int par; cin >> par;
        G[par].push_back(i);
        pow2[i+1] = (pow2[i] * 2) % MOD;
    }

    auto deq = solve(G, 0);
    for(size_t i=0; i<deq.size(); i++) {
        (ans += deq[i].b * pow2[N + 1 - cnt_depth[i]]) %= MOD;
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Smuggling Marbles
User tsutaj
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1709 Byte
Status AC
Exec Time 193 ms
Memory 178304 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 600 / 600
Status
AC × 3
AC × 20
AC × 52
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 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
s1_01.txt AC 2 ms 256 KB
s1_02.txt AC 2 ms 256 KB
s1_03.txt AC 2 ms 256 KB
s1_04.txt AC 1 ms 256 KB
s1_05.txt AC 2 ms 256 KB
s1_06.txt AC 2 ms 384 KB
s1_07.txt AC 2 ms 256 KB
s1_08.txt AC 3 ms 2048 KB
s1_09.txt AC 2 ms 768 KB
s1_10.txt AC 2 ms 384 KB
s1_11.txt AC 2 ms 256 KB
s1_12.txt AC 2 ms 256 KB
s1_13.txt AC 1 ms 256 KB
s1_14.txt AC 2 ms 384 KB
s1_15.txt AC 2 ms 384 KB
s1_16.txt AC 2 ms 384 KB
s1_17.txt AC 2 ms 384 KB
s2_01.txt AC 10 ms 1024 KB
s2_02.txt AC 3 ms 384 KB
s2_03.txt AC 68 ms 5376 KB
s2_04.txt AC 42 ms 3584 KB
s2_05.txt AC 72 ms 6400 KB
s2_06.txt AC 98 ms 7680 KB
s2_07.txt AC 62 ms 5248 KB
s2_08.txt AC 32 ms 2816 KB
s2_09.txt AC 97 ms 7424 KB
s2_10.txt AC 76 ms 6272 KB
s2_11.txt AC 81 ms 6648 KB
s2_12.txt AC 3 ms 384 KB
s2_13.txt AC 193 ms 178304 KB
s2_14.txt AC 192 ms 178304 KB
s2_15.txt AC 172 ms 160128 KB
s2_16.txt AC 10 ms 1024 KB
s2_17.txt AC 3 ms 384 KB
s2_18.txt AC 68 ms 5760 KB
s2_19.txt AC 41 ms 3584 KB
s2_20.txt AC 111 ms 8960 KB
s2_21.txt AC 119 ms 9472 KB
s2_22.txt AC 104 ms 8192 KB
s2_23.txt AC 110 ms 8960 KB
s2_24.txt AC 108 ms 11520 KB
s2_25.txt AC 103 ms 14080 KB
s2_26.txt AC 110 ms 22400 KB
s2_27.txt AC 161 ms 116608 KB
s2_28.txt AC 157 ms 107264 KB
s2_29.txt AC 187 ms 169984 KB
s2_30.txt AC 188 ms 169984 KB
s2_31.txt AC 172 ms 93312 KB
s2_32.txt AC 165 ms 93312 KB