Task: | Tree matching |
Sender: | ivan |
Submission time: | 2016-09-24 15:23:33 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.65 s | details |
#3 | ACCEPTED | 0.66 s | details |
#4 | ACCEPTED | 0.66 s | details |
#5 | ACCEPTED | 0.66 s | details |
#6 | ACCEPTED | 0.67 s | details |
#7 | ACCEPTED | 0.67 s | details |
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 includedll b1 = left.second; // root excludedll 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 |