3212 2023. 02. 22 16:41:17 zsombor Fájlrendszer cpp17 Elfogadva 40/40 93ms 14656 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, a, b;
ll ans = 1, MOD = 1e9 + 7;
vector <vector <int>> g(1e5 + 1);
vector <int> db(1e5 + 1, 0);
vector <int> sum(1e5 + 1, 0);

void dfs(int x) {
    if (!g[x].size()) return;
    a = g[x][0]; b = g[x][1];
    if (db[x] > -1 && db[a] > -1) db[b] = db[x] - db[a];
    if (db[x] > -1 && db[b] > -1) db[a] = db[x] - db[b];
    dfs(g[x][0]); dfs(g[x][1]);
    a = g[x][0]; b = g[x][1];
    if (db[a] > -1 && db[b] > -1) db[x] = db[a] + db[b];
}

void solve(int x) {
    if (db[x] > -1) sum[x] = db[x];
    if (!g[x].size()) return;
    solve(g[x][0]); solve(g[x][1]);
    a = g[x][0]; b = g[x][1];
    if (db[x] == -1) {
        sum[x] = sum[a] + sum[b];
        return;
    }
    if (db[a] > -1) return;
    ans *= db[x] - sum[a] - sum[b] + 1;
    ans %= MOD;
    return;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> db[i];
        if (a) g[a].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (g[i].size() == 1) g[i].push_back(0);
    dfs(1); dfs(1);
    solve(1);
    cout << ans;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 6ms 8096 KiB
2 Elfogadva 0/0 46ms 10548 KiB
3 Elfogadva 1/1 4ms 8360 KiB
4 Elfogadva 1/1 4ms 8616 KiB
5 Elfogadva 1/1 4ms 9072 KiB
6 Elfogadva 1/1 4ms 8928 KiB
7 Elfogadva 2/2 4ms 9136 KiB
8 Elfogadva 2/2 7ms 9192 KiB
9 Elfogadva 3/3 8ms 9404 KiB
10 Elfogadva 3/3 8ms 9720 KiB
11 Elfogadva 3/3 9ms 10364 KiB
12 Elfogadva 3/3 12ms 10544 KiB
13 Elfogadva 4/4 28ms 11272 KiB
14 Elfogadva 4/4 39ms 11832 KiB
15 Elfogadva 4/4 48ms 12452 KiB
16 Elfogadva 4/4 93ms 14656 KiB
17 Elfogadva 4/4 92ms 14588 KiB