Submission details
Task:Tree matching
Sender:ivan
Submission time:2016-09-24 15:23:33 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.65 sdetails
#3ACCEPTED0.66 sdetails
#4ACCEPTED0.66 sdetails
#5ACCEPTED0.66 sdetails
#6ACCEPTED0.67 sdetails
#7ACCEPTED0.67 sdetails

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
using ll = long long;
ll modulo = 1e9 + 7;
vector< pair<int, int> > v;
pair<ll, ll> calculate(int node) {
if (v[node].first == -1 && v[node].second == -1) {
return make_pair(0, 1);
}
pair<ll, ll> left = make_pair(0, 0);
if (v[node].first != -1)
left = calculate(v[node].first);
pair<ll, ll> right = make_pair(0, 0);
if (v[node].second != -1)
right = calculate(v[node].second);
ll a1 = left.first; // root included
ll b1 = left.second; // root excluded
ll a2 = right.first;
ll b2 = right.second;
ll included = 0;
ll excluded = 0;
if (v[node].first == -1) {
excluded = (a2 + b2) % modulo;
included = b2;
} else if (v[node].second == -1) {
excluded = (a1 + b1) % modulo;
included = b1;
} else {
excluded = ((a1 + b1) * (a2 + b2)) % modulo;
included = (((b1) * (a2 + b2)) % modulo + ((a1 + b1) * (b2)) % modulo) % modulo;
}
// cout << node << " " << included << " " << excluded << endl;
return make_pair(included, excluded);
}
int main(int argc, char *argv[])
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
v.push_back(make_pair(a - 1, b - 1));
}
pair<ll, ll> res = calculate(0);
cout << (res.first + res.second) % modulo << endl;
return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
7
5 6
0 0
4 0
2 0
...

correct output
19

user output
19

Test 2

Verdict: ACCEPTED

input
1000000
406968 281253
108264 0
0 0
0 0
...

correct output
159944844

user output
159944844

Test 3

Verdict: ACCEPTED

input
1000000
1000000 325587
791377 324030
873422 0
0 0
...

correct output
114625606

user output
114625606

Test 4

Verdict: ACCEPTED

input
1000000
495129 959931
0 703069
862854 0
0 423221
...

correct output
922109659

user output
922109659

Test 5

Verdict: ACCEPTED

input
1000000
667150 768657
0 528730
716704 103616
554625 0
...

correct output
331516797

user output
331516797

Test 6

Verdict: ACCEPTED

input
1000000
490726 891332
0 988621
0 469251
224815 393797
...

correct output
831971669

user output
831971669

Test 7

Verdict: ACCEPTED

input
1000000
554662 668
0 0
0 0
0 806138
...

correct output
593438800

user output
593438800