Submission details
Task:Tree matching
Sender:eax511
Submission time:2016-09-24 13:52:09 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#20.17 sdetails
#30.17 sdetails
#40.15 sdetails
#50.17 sdetails
#60.17 sdetails
#70.17 sdetails

Compiler report

input/code.cpp: In function 'll cnt(ll, ll*, ll*)':
input/code.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(c[i][0]!=-1)cnt(c[i][0],a,a+1);
                ^
input/code.cpp:10:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(c[i][1]!=-1)cnt(c[i][1],b,b+1);
                ^
input/code.cpp: In function 'int main()':
input/code.cpp:18:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%llu",&n);
                   ^
input/code.cpp:20:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%llu %llu",c[i]+0,c[i]+1);
                                     ^

Code

#include <stdio.h>
typedef unsigned long long N;
typedef N ll;
const ll M=1e9+7;
ll c[101010][2];
ll cnt(ll i,ll* x, ll* y){
  *x=1,*y=0;
  ll a[2]={0,1},b[2]={0,1};
  if(c[i][0]!=-1)cnt(c[i][0],a,a+1);
  if(c[i][1]!=-1)cnt(c[i][1],b,b+1);
  *x=(a[1]*b[1])%M;
  *y=(*x+((a[0]*b[1])%M+(b[0]*a[1])%M)%M)%M;
  //printf("%llu: %llu %llu\n",i,*x,*y);
  return *y;
}
int main(){
  N n,i;
  scanf("%llu",&n);
  for(i=0;i<n;++i){
    scanf("%llu %llu",c[i]+0,c[i]+1);
    --c[i][0],--c[i][1];
  }
  printf("%llu\n",cnt(0,&n,&i));
  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:

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

correct output
159944844

user output
(empty)

Test 3

Verdict:

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

correct output
114625606

user output
(empty)

Test 4

Verdict:

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

correct output
922109659

user output
(empty)

Test 5

Verdict:

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

correct output
331516797

user output
(empty)

Test 6

Verdict:

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

correct output
831971669

user output
(empty)

Test 7

Verdict:

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

correct output
593438800

user output
(empty)