QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85925#5659. Watching CowflixBird12.5 137ms37496kbC++142.2kb2023-03-08 21:17:442023-03-08 21:17:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-08 21:17:47]
  • 评测
  • 测评结果:12.5
  • 用时:137ms
  • 内存:37496kb
  • [2023-03-08 21:17:44]
  • 提交

answer

#include<bits/stdc++.h>
#include<queue>
#define N 200000
using namespace std;
const int inf=1e9;
int n,deep[N+5],dfn[N+5],edfn[N+5],f[N+5][18],fa[N+5],st[N+5],top,ans,dp[N+5][2],k;
bool vis[N+5];
vector<int> e[N+5],v,now,E[N+5];
char s[N+5];
inline void dfs(int x,int fa)
{
	static int tot;
	deep[x]=deep[fa]+1,dfn[x]=++tot,f[x][0]=fa;
	for(int i=1;i<18;++i) f[x][i]=f[f[x][i-1]][i-1];
	for(int y:e[x]) if(y!=fa) dfs(y,x);
	edfn[x]=tot;
}
inline int lca(int u,int v)
{
	if(deep[u]<deep[v]) swap(u,v);
	for(int i=17,k=deep[u]-deep[v];~i;--i) if(k>>i&1) u=f[u][i];
	if(u==v) return u;
	for(int i=17;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}
inline void dfs1(int x,bool p)
{
	s[x]='0'^p,vis[x]=s[x]=='1' && s[fa[x]]=='1' && deep[x]-deep[fa[x]]-1<=k;
	for(int y:E[x])
	{
		if(p==1) dp[y][1]+=min(0,deep[y]-deep[x]-1-k);
		dfs1(y,dp[y][1]<=dp[y][0]);
	}	
}
int main()
{
	scanf("%d %s",&n,s+1);
	for(int i=1,u,v;i<n;++i)
	{
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i) if(s[i]=='1') v.push_back(i),++ans;
	if(v.empty())
	{
		for(int i=1;i<=n;++i) puts("0");
		return 0;
	}
	dfs(1,0);
	sort(v.begin(),v.end(),[&](int a,int b) {return dfn[a]<dfn[b];});
	for(int i=(int)v.size()-1;i;--i) v.push_back(lca(v[i-1],v[i]));
	sort(v.begin(),v.end(),[&](int a,int b) {return dfn[a]<dfn[b];});
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int x:v)
	{
		while(top && edfn[st[top]]<dfn[x]) --top;
		if(top) E[fa[x]=st[top]].push_back(x);
		st[++top]=x;
	}
	now=v,reverse(now.begin(),now.end());
	for(k=1;k<=n;++k)
	{
		vector<int> root,nxt;
		for(int x:now)
			if(s[x]=='0') dp[x][0]=0,dp[x][1]=k+1;
			else dp[x][0]=inf,dp[x][1]=1;
		for(int x:now)
			if(!fa[x] || s[fa[x]]=='1') root.push_back(x);
			else dp[fa[x]][0]+=min(dp[x][0],dp[x][1]),
				dp[fa[x]][1]+=min(dp[x][0],dp[x][1]+min(0,deep[x]-deep[fa[x]]-1-k));
		
		for(int x:root)
		{
			if(fa[x]) dp[x][1]+=min(0,deep[x]-deep[fa[x]]-1-k);
			ans+=min(dp[x][0],dp[x][1]);
			dfs1(x,dp[x][1]<=dp[x][0]);
		}
		for(int x:now) if(!vis[x]) nxt.push_back(x);
		now=nxt;
		printf("%d\n",ans);
	}
	return 0;
}

詳細信息

Test #1:

score: 4.16667
Accepted
time: 4ms
memory: 13040kb

input:

5
10001
1 2
2 3
3 4
4 5

output:

4
6
8
9
10

result:

ok 5 number(s): "4 6 8 9 10"

Test #2:

score: 4.16667
Accepted
time: 2ms
memory: 12992kb

input:

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

output:

4
6
8
9
10
11
12

result:

ok 7 numbers

Test #3:

score: 0
Wrong Answer
time: 25ms
memory: 13852kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...

output:

711
836
943
1039
1118
1187
1244
1294
1341
1384
1425
1465
1504
1543
1582
1620
1657
1693
1728
1761
1793
1825
1857
1888
1918
1947
1976
2004
2032
2059
2085
2111
2136
2160
2183
2206
2228
2250
2272
2294
2315
2335
2354
2372
2390
2408
2425
2442
2458
2473
2488
2502
2515
2527
2538
2549
2559
2569
2579
2589
259...

result:

wrong answer 2nd numbers differ - expected: '837', found: '836'

Test #4:

score: 0
Wrong Answer
time: 39ms
memory: 13924kb

input:

5000
0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...

output:

890
1226
1422
1534
1604
1661
1712
1760
1806
1850
1893
1935
1974
2012
2049
2085
2121
2156
2191
2225
2258
2290
2321
2351
2380
2409
2437
2464
2491
2517
2542
2566
2589
2611
2633
2655
2676
2696
2715
2734
2753
2771
2789
2806
2822
2838
2854
2869
2883
2896
2908
2919
2929
2938
2947
2956
2965
2973
2980
2986
2...

result:

wrong answer 3rd numbers differ - expected: '1433', found: '1422'

Test #5:

score: 0
Wrong Answer
time: 31ms
memory: 13832kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...

output:

794
1022
1175
1277
1345
1398
1449
1493
1535
1576
1616
1655
1693
1730
1766
1802
1837
1871
1904
1936
1968
2000
2032
2064
2095
2126
2157
2187
2217
2246
2274
2301
2327
2352
2377
2401
2424
2447
2469
2491
2512
2532
2551
2570
2588
2605
2621
2636
2650
2664
2677
2689
2700
2710
2719
2727
2735
2742
2748
2753
2...

result:

wrong answer 2nd numbers differ - expected: '1025', found: '1022'

Test #6:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12231
13860
15148
16183
17002
17655
18214
18696
19102
19456
19775
20072
20347
20606
20851
21087
21314
21532
21742
21949
22148
22345
22538
22729
22917
23102
23284
23464
23643
23820
23995
24169
24342
24513
24684
24855
25025
25195
25364
25532
25700
25867
26033
26199
26364
26529
26694
26858
27021
27184
...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15993
21806
24974
26419
27202
27701
28065
28351
28594
28810
29016
29217
29414
29607
29798
29987
30176
30364
30550
30735
30920
31104
31287
31470
31652
31833
32013
32192
32371
32549
32726
32902
33077
33251
33424
33596
33767
33937
34106
34275
34444
34613
34781
34949
35116
35283
35449
35614
35779
35944
...

result:


Test #11:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14608
18444
21205
22991
23778
24191
24497
24733
24939
25133
25321
25507
25692
25877
26062
26246
26430
26614
26797
26980
27163
27346
27528
27710
27891
28072
28252
28432
28612
28791
28969
29147
29324
29501
29677
29852
30027
30202
30377
30551
30724
30896
31068
31239
31410
31581
31751
31920
32088
32256
...

result:


Test #12:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12198
13813
15081
16124
16978
17662
18240
18733
19155
19543
19898
20226
20527
20815
21087
21347
21601
21847
22086
22318
22549
22776
23001
23224
23444
23661
23875
24088
24298
24506
24713
24920
25124
25328
25531
25733
25934
26134
26333
26532
26731
26930
27129
27327
27524
27721
27917
28112
28306
28500
...

result:


Test #13:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16072
21895
25013
26500
27330
27832
28203
28499
28755
28985
29198
29405
29605
29802
29997
30192
30386
30579
30771
30962
31152
31341
31529
31717
31904
32090
32276
32461
32645
32829
33012
33194
33375
33555
33735
33914
34092
34269
34445
34620
34795
34969
35143
35317
35491
35664
35836
36007
36177
36346
...

result:


Test #14:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14721
18667
21478
23280
24154
24648
24990
25263
25502
25727
25944
26159
26373
26586
26798
27009
27219
27429
27638
27846
28053
28260
28466
28671
28876
29080
29283
29485
29686
29886
30085
30283
30480
30676
30872
31068
31264
31459
31653
31846
32039
32231
32422
32613
32803
32993
33182
33370
33557
33744
...

result:


Test #15:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12121
13751
15052
16070
16874
17540
18087
18556
18962
19327
19660
19965
20252
20511
20755
20990
21220
21441
21657
21869
22077
22281
22480
22676
22870
23058
23243
23426
23609
23790
23969
24147
24324
24500
24676
24852
25027
25201
25374
25546
25717
25887
26057
26227
26396
26564
26732
26899
27066
27232
...

result:


Test #16:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16192
22044
25126
26594
27412
27894
28249
28526
28771
28991
29199
29401
29596
29790
29980
30169
30356
30543
30730
30917
31102
31286
31469
31651
31832
32012
32191
32369
32547
32724
32901
33078
33255
33431
33607
33782
33956
34129
34301
34472
34643
34814
34984
35153
35321
35488
35654
35819
35983
36146
...

result:


Test #17:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14705
18631
21402
23190
24070
24558
24916
25198
25453
25698
25940
26181
26422
26662
26902
27141
27380
27618
27855
28091
28326
28561
28795
29028
29261
29493
29724
29954
30184
30413
30642
30870
31097
31323
31548
31772
31996
32219
32441
32662
32882
33102
33321
33540
33758
33976
34193
34409
34624
34838
...

result:


Test #18:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12282
13869
15131
16178
17003
17668
18232
18711
19131
19501
19834
20136
20414
20671
20916
21150
21372
21583
21791
21998
22202
22401
22598
22791
22983
23171
23358
23543
23725
23906
24084
24260
24435
24610
24783
24955
25126
25296
25466
25636
25806
25975
26143
26310
26476
26641
26805
26969
27132
27294
...

result:


Test #19:

score: 4.16667
Accepted
time: 63ms
memory: 25780kb

input:

100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111
114
117
120
123
126
129
132
135
138
141
144
147
150
153
156
159
162
165
168
171
174
177
180
183
186
189
192
195
198
201
204
207
210
213
216
219
222
225
228
231
234
237
240
243
246
249
252
25...

result:

ok 100000 numbers

Test #20:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

32208
43696
49713
52520
53998
54886
55513
55976
56358
56691
57001
57294
57579
57856
58127
58394
58660
58925
59190
59455
59720
59984
60247
60509
60771
61032
61292
61551
61809
62066
62322
62577
62831
63085
63338
63590
63841
64091
64340
64589
64837
65084
65331
65578
65824
66069
66313
66556
66798
67039
...

result:


Test #21:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

29187
37000
42415
45938
47448
48238
48758
49142
49465
49759
50040
50318
50594
50869
51142
51415
51687
51958
52229
52500
52771
53041
53311
53581
53851
54121
54390
54659
54927
55194
55460
55725
55990
56254
56517
56779
57041
57303
57565
57826
58086
58346
58605
58863
59120
59377
59633
59888
60143
60398
...

result:


Test #22:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

24124
27216
29570
31464
32986
34215
35228
36084
36829
37487
38057
38553
39004
39434
39835
40216
40580
40928
41259
41578
41886
42186
42482
42774
43062
43346
43623
43898
44172
44443
44711
44978
45244
45508
45772
46035
46298
46560
46822
47083
47344
47604
47863
48122
48380
48638
48895
49151
49407
49662
...

result:


Test #23:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

32229
43868
49981
52833
54293
55151
55732
56171
56548
56889
57198
57493
57774
58047
58318
58587
58856
59125
59393
59660
59926
60191
60455
60719
60983
61247
61510
61772
62034
62295
62556
62816
63075
63334
63592
63849
64106
64362
64618
64873
65127
65380
65632
65883
66133
66382
66630
66877
67124
67370
...

result:


Test #24:

score: 0
Wrong Answer
time: 137ms
memory: 37496kb

input:

200000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111
114
117
120
123
126
129
132
135
138
141
144
147
150
153
156
159
162
165
168
171
174
177
180
183
186
189
192
195
198
201
204
207
210
213
216
219
222
225
228
231
234
237
240
243
246
249
252
25...

result:

wrong answer 6239th numbers differ - expected: '18720', found: '18719'