Task: | Tree matching |
Sender: | HopeICanCode |
Submission time: | 2016-09-24 16:18:22 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.07 s | details |
#2 | WRONG ANSWER | 0.45 s | details |
#3 | WRONG ANSWER | 0.46 s | details |
#4 | WRONG ANSWER | 0.47 s | details |
#5 | WRONG ANSWER | 0.47 s | details |
#6 | WRONG ANSWER | 0.47 s | details |
#7 | WRONG ANSWER | 0.45 s | details |
Compiler report
input/code.cpp: In function 'int64 solve(int)': input/code.cpp:20:47: warning: unused variable 'nComb' [-Wunused-variable] int left = child[u][0], right = child[u][1], nComb = 0; ^
Code
#include <bits/stdc++.h> #define UNVISITED -1 #define BIGINT 1 << 25 #define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15); using namespace std; typedef long long int64; typedef pair<int, int> ii; const int MOD = 1000000007; vector<int64> comb; // total combination, combination when combines neither child vector< vector<int> > child; int64 solve(int u){ if(u == -1) return 0; if(u == 0) return 1; if(comb[u] != -1) return comb[u]; comb[u] = 0; int left = child[u][0], right = child[u][1], nComb = 0; comb[u] += solve(left) * solve(right); comb[u] %= MOD; comb[u] += solve(child[left][0]) * solve(child[left][1]) * solve(right); comb[u] %= MOD; comb[u] += solve(left) * solve(child[right][0]) * solve(child[right][1]); comb[u] %= MOD; /* if(left != 0 && right != 0){ // don't connect either child nComb = solve(left) * solve(right); comb[u] = (comb[u] + nComb) % MOD; // connect left child // then we can ignore all grand child of left child and only consider right siblings // or we can consider grand children of left child and consider right siblings nComb = solve(child[left][0]) * solve(child[left][1]) * solve(right); comb[u] = (comb[u] + nComb) % MOD; // connect left child nComb = solve(left) * solve(child[right][0]) * solve(child[right][1]); comb[u] = (comb[u] + nComb) % MOD; } else if(left != 0){ // don't connect left nComb = solve(left); comb[u] = (comb[u] + nComb) % MOD; // connect left nComb = solve(child[left][0]) * solve(child[left][1]); comb[u] = (comb[u] + nComb) % MOD; } else if(right != 0){ // don't connect right nComb = solve(right); comb[u] = (comb[u] + nComb) % MOD; // connect left nComb = solve(child[right][0]) * solve(child[right][1]); comb[u] = (comb[u] + nComb) % MOD; } else { comb[u] = 1; } */ return comb[u]; } int main(){ _ int n; cin >> n; comb.assign(n+1, (int64)UNVISITED); child.assign(n+1, vector<int> (2, -1)); for(int i = 1; i <= n; ++i) cin >> child[i][0] >> child[i][1]; //for(int i = 0; i <= n; ++i) //cout << i << ": " << solve(i) << endl; cout << solve(1) << 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: WRONG ANSWER
input |
---|
1000000 406968 281253 108264 0 0 0 0 0 ... |
correct output |
---|
159944844 |
user output |
---|
339556176 |
Test 3
Verdict: WRONG ANSWER
input |
---|
1000000 1000000 325587 791377 324030 873422 0 0 0 ... |
correct output |
---|
114625606 |
user output |
---|
-947618854 |
Test 4
Verdict: WRONG ANSWER
input |
---|
1000000 495129 959931 0 703069 862854 0 0 423221 ... |
correct output |
---|
922109659 |
user output |
---|
-606742029 |
Test 5
Verdict: WRONG ANSWER
input |
---|
1000000 667150 768657 0 528730 716704 103616 554625 0 ... |
correct output |
---|
331516797 |
user output |
---|
859901406 |
Test 6
Verdict: WRONG ANSWER
input |
---|
1000000 490726 891332 0 988621 0 469251 224815 393797 ... |
correct output |
---|
831971669 |
user output |
---|
-180933637 |
Test 7
Verdict: WRONG ANSWER
input |
---|
1000000 554662 668 0 0 0 0 0 806138 ... |
correct output |
---|
593438800 |
user output |
---|
-353562136 |