CSES - E4590 2016 2 - Results
Submission details
Task:Tree matching
Sender:eax511
Submission time:2016-09-24 14:25:36 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.28 sdetails
#3ACCEPTED0.29 sdetails
#4ACCEPTED0.32 sdetails
#5ACCEPTED0.31 sdetails
#6ACCEPTED0.29 sdetails
#7ACCEPTED0.30 sdetails

Compiler report

input/code.cpp: In function 'll cnt(ll)':
input/code.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(c[i].l!=-1)cnt(c[i].l),c[i].a[0]=c[c[i].l].f[0],c[i].a[1]=c[c[i].l].f[1];
               ^
input/code.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(c[i].r!=-1)cnt(c[i].r),c[i].b[0]=c[c[i].r].f[0],c[i].b[1]=c[c[i].r].f[1];
               ^
input/code.cpp: In function 'int main()':
input/code.cpp:22:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%llu",&n);
                   ^
input/code.cpp:24:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%llu %llu",&c[i].l,&c[i].r);
                                       ^

Code

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