QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282721#7607. The Doubling Game 2light_ink_dotsWA 920ms185780kbC++143.0kb2023-12-12 20:58:202023-12-12 20:58:21

Judging History

你现在查看的是最新测评结果

  • [2023-12-12 20:58:21]
  • 评测
  • 测评结果:WA
  • 用时:920ms
  • 内存:185780kb
  • [2023-12-12 20:58:20]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+100;
const int mod=1e9+7;
#define int long long
int n;
vector<int>v[N];
int dp[N][20],g[N][20],h[N];
int f[N];
int mex(const vector<int>&a){
    static int vis[30];
    memset(vis,0,sizeof(vis));
    for(int x:a)
        for(int i=0;i<=x;i++) vis[i]++;
    for(int k=0;k<=20;k++){
        for(int j=0;j<=k;j++){
            if(vis[j]-(k+1)+j<0)return k;
        }
    }
}
void pfs(int x,int fa){
    vector<int>s;
    for(auto y:v[x]){
        if(y==fa) continue;
        pfs(y,x);
        s.push_back(f[y]);
    }
    f[x]=mex(s);
    // cerr<<"? "<<x<<" "<<f[x]<<endl;
}
int d[N][20],tg[N][20];
void dfs(int x,int fa){
    vector<int>out;
    for(int y:v[x]) if(y!=fa) out.push_back(y);
    sort(out.begin(),out.end(),[&](int u,int v){
        return f[u]<f[v];
    });
    // h[x]=1;
    for(auto y:out)dfs(y,x);
    int lim=f[x]+1;
    for(int s=0;s<(1<<(lim+1));s++){
        memset(d[s],0,sizeof(d[s]));
    }
    d[0][0]=1;
    for(auto y:out){
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            memset(tg[s],0,sizeof(tg[s]));
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++) {
            for(int j=0;j<=lim+1;j++){
                tg[s][j]=d[s][j]*h[y]%mod;
            }
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            for(int i=0;i<=min(f[y],lim);i++){
                if((s>>i)&1) continue;
                for(int j=0;j<=lim+1;j++){
                    (tg[s+(1<<i)][j]+=d[s][j]*dp[y][i])%=mod;
                }
                // for(int j=0;j<=lim+1;j++){
        // if(x==1&&s==0) cerr<<tg[0][1]<<endl;
                    (tg[s][i+1]+=d[s][0]*g[y][i])%=mod;    
                    // if(x==4&&s==0&&i==1){
                    //     cerr<<"?? "<<tg[s][i+1]<<" "<<d[s][0]<<" "<<g[y][i]<<endl;
                    // }
                // }
            }
        }
        for(int s=0;s<(1<<min(lim,f[y]+1));s++){
            memcpy(d[s],tg[s],sizeof(d[s]));
        }
    }
    for(int i=0;i<=lim;i++){
        dp[x][i]=d[(1<<i)-1][0];
        (h[x]+=dp[x][i])%=mod;
    }
    // cerr<<"??? "<<x<<" "<<g[2][0]<<"  "<<d[0][1]<<endl;
    // if(x==4) cerr<<"!!! "<<d[2][0]<<" "<<dp[1][1]<<endl;
    for(int i=0;i<=lim+1;i++){
        //j 空
        for(int j=0;j<i;j++){
            g[x][j]+=d[(1<<i)-(1<<j)-1][i+1];
    // if(x==4&&j==0) cerr<<i<<" "<<j<<" "<<d[(1<<i)-(1<<j)-1][i+1]<<" "<<d[0][2]<<" "<<g[1][1]<<endl;
        }
        for(int j=0;j<i;j++){
            (g[x][j]+=d[(1<<i)-(1<<j)-1][0])%=mod;
        }
        (h[x]+=d[(1<<i)-1][i+1])%=mod;
    }
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        v[x].push_back(y),v[y].push_back(x);
    }
    int rt=1;
    pfs(rt,0);
    dfs(rt,0);
    cerr<<g[4][0]<<" "<<g[1][1]<<endl;
    cout<<h[rt];
}
/*
3
1 2
2 3

5
1 2
1 3
1 4
4 5
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 10592kb

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

score: 0
Accepted
time: 4ms
memory: 10516kb

input:

1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 10580kb

input:

128
11 32
116 81
65 4
117 47
5 81
104 30
61 8
82 59
95 20
92 29
29 127
97 39
123 33
59 128
115 33
83 67
74 16
77 33
64 73
124 123
8 127
61 51
101 122
35 90
119 116
112 27
81 93
109 123
54 1
119 100
116 16
65 47
67 27
22 105
76 87
36 39
27 96
72 31
91 123
21 105
118 12
110 48
121 72
14 115
24 16
106 ...

output:

508800953

result:

ok single line: '508800953'

Test #4:

score: 0
Accepted
time: 0ms
memory: 10612kb

input:

256
53 177
57 242
74 90
107 104
209 169
132 70
152 142
71 168
143 99
91 130
202 140
49 165
209 193
209 137
159 188
247 48
49 21
20 208
155 185
120 231
83 87
37 84
143 18
106 8
114 79
191 158
208 256
133 252
215 92
199 108
166 168
39 217
85 69
204 139
100 75
111 6
230 198
79 130
26 155
155 38
55 81
1...

output:

999869740

result:

ok single line: '999869740'

Test #5:

score: 0
Accepted
time: 0ms
memory: 10740kb

input:

512
507 193
168 152
48 369
273 170
101 349
160 261
438 197
446 224
125 264
210 131
272 218
361 85
226 119
57 33
229 89
37 317
130 417
30 470
435 300
499 417
132 260
196 430
119 117
157 260
207 151
368 277
188 371
214 330
484 228
96 94
97 442
251 461
443 248
163 207
306 147
346 90
457 112
436 222
364...

output:

37387055

result:

ok single line: '37387055'

Test #6:

score: 0
Accepted
time: 0ms
memory: 10952kb

input:

1024
340 598
1 851
245 819
414 736
996 316
300 284
924 407
532 557
362 178
1006 469
397 373
742 77
112 37
406 892
703 666
496 825
1002 100
875 856
263 975
227 6
288 389
661 437
160 626
833 770
912 837
405 628
466 686
45 629
59 13
163 991
1017 422
208 247
344 376
709 956
570 272
996 954
518 454
267 3...

output:

689180079

result:

ok single line: '689180079'

Test #7:

score: 0
Accepted
time: 0ms
memory: 11376kb

input:

2048
2046 1942
589 1449
1593 1983
936 414
387 184
1962 1237
1986 635
573 1619
1598 1109
458 836
1123 1563
1502 519
1467 347
1815 864
980 405
709 433
1682 211
1967 1915
1089 1902
564 211
128 1004
1568 315
293 494
1552 1772
1641 1157
431 1899
1334 1623
161 1870
885 1330
1863 502
1761 1643
692 1759
118...

output:

275839338

result:

ok single line: '275839338'

Test #8:

score: 0
Accepted
time: 3ms
memory: 12076kb

input:

4096
2546 3568
3084 3426
1262 2128
1773 1455
425 3750
3444 3265
3099 464
3479 3651
639 1727
2486 2768
1165 1905
1847 2626
1335 3938
2550 1594
1520 1758
3771 2227
3486 60
381 383
1268 2829
1884 3468
3195 2892
983 31
584 2599
2811 1876
1875 3310
3184 2941
2893 202
1305 1926
1019 1639
3529 1998
2129 12...

output:

99235843

result:

ok single line: '99235843'

Test #9:

score: 0
Accepted
time: 3ms
memory: 13672kb

input:

8192
5663 2164
3712 1600
336 2388
1971 4169
1579 7319
496 8080
5305 982
5508 5777
5324 6680
4636 6745
7295 6086
6948 388
5239 811
1875 7271
5755 2864
2933 795
6448 6716
3016 302
2474 2937
6355 5936
4973 4064
2920 2318
6254 4090
665 2500
961 8180
5416 6371
4958 5430
7905 5013
4373 3068
6557 3867
3056...

output:

79832799

result:

ok single line: '79832799'

Test #10:

score: 0
Accepted
time: 16ms
memory: 16756kb

input:

16384
4535 8823
5344 1240
5793 15361
8423 14130
14595 11420
12195 1332
9712 4829
9533 14608
1328 14962
13846 1173
12823 5702
3518 9298
3235 13113
14312 3915
3439 9003
4667 5401
3819 2395
13827 981
3557 11804
7369 11344
15524 1435
4706 15539
12838 2109
4986 5367
2766 4313
6802 12338
12059 3998
6327 5...

output:

732760598

result:

ok single line: '732760598'

Test #11:

score: 0
Accepted
time: 24ms
memory: 22892kb

input:

32768
18706 23242
17650 5918
17278 24553
13070 18006
22702 10359
7113 13886
25578 16957
28955 27352
7353 6627
24042 21572
4744 30083
29267 16077
19328 1154
32271 23711
22390 3651
19272 7150
19081 13949
22123 4853
17958 18148
27675 28239
29486 26616
14292 23782
12790 18303
25184 9656
2671 13229
21875...

output:

383548244

result:

ok single line: '383548244'

Test #12:

score: 0
Accepted
time: 44ms
memory: 35260kb

input:

65536
58488 63309
5892 23044
42057 26219
45788 13164
16585 3001
4262 20408
60289 43446
44684 60172
60763 38228
56279 19103
45476 53988
42692 16285
17169 4001
23321 935
41892 8086
46236 15394
679 21542
26763 36111
47813 62044
22621 35997
6381 14778
17034 21699
54381 53287
35694 34830
14902 30504
5158...

output:

440039161

result:

ok single line: '440039161'

Test #13:

score: 0
Accepted
time: 0ms
memory: 10620kb

input:

2
2 1

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 111ms
memory: 59456kb

input:

131072
51230 116074
14356 18985
97302 87862
20350 65669
81694 54472
94257 44656
77121 118912
81235 115171
106881 104061
82683 25663
68305 12450
29336 62646
32572 74421
102407 112028
122054 79222
70569 123539
8651 78501
204 34510
69520 18129
55082 68106
51505 114323
100795 60383
61023 59864
57018 337...

output:

776456918

result:

ok single line: '776456918'

Test #15:

score: 0
Accepted
time: 284ms
memory: 106920kb

input:

262144
131863 89153
74747 38646
187112 232634
203855 116743
1197 3109
104299 20430
195824 110378
144817 150658
187558 66008
261366 71448
227156 246386
4149 219771
47465 87425
185952 150310
20653 103389
4917 221350
124004 104544
162181 144076
79557 176106
88679 240655
234082 52601
205629 150797
20194...

output:

777533279

result:

ok single line: '777533279'

Test #16:

score: 0
Accepted
time: 310ms
memory: 185780kb

input:

300000
200042 33358
146127 282853
18162 208274
88763 197176
219535 47504
18973 156413
135038 231317
236314 79984
54777 75970
263068 185590
178314 16697
46633 171708
244101 108105
262612 237866
278911 257361
223742 114478
189208 195065
226678 182830
43889 137857
43488 17945
129846 57509
272492 132190...

output:

528233774

result:

ok single line: '528233774'

Test #17:

score: 0
Accepted
time: 325ms
memory: 158488kb

input:

300000
176764 78952
106987 49376
199197 145137
284233 133549
153566 146492
192389 171608
126109 165447
243592 22382
235466 121116
184443 97521
282334 9814
156 188663
107376 36037
157844 51710
62907 257468
246294 216846
219236 183284
216849 220858
269297 95886
219479 273154
165259 18296
162990 56046
...

output:

750813860

result:

ok single line: '750813860'

Test #18:

score: 0
Accepted
time: 309ms
memory: 142380kb

input:

300000
158309 149704
128435 163070
84245 49253
264263 44739
68743 180951
108361 147453
240926 297856
89945 260111
277457 169826
291582 125079
277648 144954
101400 245176
23891 241280
63493 241546
201991 83439
148391 183664
21371 262320
204841 29292
277535 194623
82560 91044
150547 79025
123803 68605...

output:

580868875

result:

ok single line: '580868875'

Test #19:

score: 0
Accepted
time: 329ms
memory: 128616kb

input:

300000
199668 175926
193518 215061
170371 258103
194712 162222
88766 94800
184812 295037
168857 181854
69199 242470
1818 80752
69395 194806
57376 42758
141192 88538
33986 256933
69427 76218
185239 91491
285920 41676
51905 1936
239856 132282
227388 41622
272706 124375
32038 284692
135219 69014
34936 ...

output:

381083020

result:

ok single line: '381083020'

Test #20:

score: -100
Wrong Answer
time: 920ms
memory: 177320kb

input:

300000
67567 276022
264241 227037
38178 145820
228201 233793
98899 138819
98797 261326
115390 242282
211578 259087
45319 276116
122811 28871
50088 69991
37258 200859
136470 175283
260338 91948
67384 212375
40231 149234
232658 26091
154421 76753
112123 10499
206637 278186
61238 227139
159931 11377
15...

output:

0

result:

wrong answer 1st lines differ - expected: '526946130', found: '0'