QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#86019#5659. Watching CowflixAFewSuns16.666667 125ms24444kbC++144.2kb2023-03-09 07:53:012023-03-09 07:53:04

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-09 07:53:04]
  • 评测
  • 测评结果:16.666667
  • 用时:125ms
  • 内存:24444kb
  • [2023-03-09 07:53:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 1e9
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
vector<ll> vec[200020];
ll n,fa[200020],son[200020],pre[200020],suf[200020],w[200020];
ll siz[200020],st[200020],top=0,dp[200020][2];
char s[200020];
bl ck[200020];
void dfs0(ll u){
	ll lst=0;
	siz[u]=1;
	fr(i,0,(ll)vec[u].size()-1){
		ll v=vec[u][i];
		if(v==fa[u]) continue;
		fa[v]=u;
		if(lst){
			pre[v]=lst;
			suf[lst]=v;
		}
		else son[u]=v;
		dfs0(v);
		lst=v;
	}
}
void del(ll u,ll v){
	if(son[u]==v) son[u]=suf[v];
	if(pre[v]) suf[pre[v]]=suf[v];
	if(suf[v]) pre[suf[v]]=pre[v];
}
void ins(ll u,ll v){
	pre[son[u]]=v;
	suf[v]=son[u];
	pre[v]=0;
	son[u]=v;
	fa[v]=u;
}
void cut(ll u){
	for(ll v=son[u];v;v=suf[v]){
		cut(v);
		if(ck[v]) continue;
		if(!son[v]||!suf[son[v]]){
			ll vv=son[v];
			del(u,v);
			if(vv){
				ins(u,vv);
				w[vv]+=w[v]+siz[v];
			}
		}
	}
}
void dfs1(ll u,ll k){
	dp[u][0]=dp[u][1]=inf;
	ll sum0=0,sum1=0,minn=inf;
	for(ll v=son[u];v;v=suf[v]){
		dfs1(v,k);
		ll tmp=min(dp[v][0],dp[v][1]);
		sum0+=tmp;
		if((dp[v][1]+w[v]-k)<=tmp) sum1+=dp[v][1]+w[v]-tmp-k;
		minn=min(minn,dp[v][1]+w[v]-tmp-k);
	}
	dp[u][0]=sum0;
	dp[u][1]=sum0+siz[u]+k;
	if(minn<=0) dp[u][1]=min(dp[u][1],sum0+sum1+siz[u]+k);
	else dp[u][1]=min(dp[u][1],sum0+minn+siz[u]+k);
	if(ck[u]) dp[u][0]=inf;
}
void dfs2(ll u,ll col,ll k){
	ll sum0=0,sum1=0,minn=inf,pos;
	for(ll v=son[u];v;v=suf[v]){
		ll tmp=min(dp[v][0],dp[v][1]);
		sum0+=tmp;
		if((dp[v][1]+w[v]-k)<=tmp) sum1+=dp[v][1]+w[v]-tmp-k;
		if(minn>(dp[v][1]+w[v]-tmp-k)){
			minn=dp[v][1]+w[v]-tmp-k;
			pos=v;
		}
	}
	if(!col){
		for(ll v=son[u];v;v=suf[v]){
			if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
			else dfs2(v,1,k);
		}
	}
	else{
		if(dp[u][1]==(sum0+siz[u]+k)){
			for(ll v=son[u];v;v=suf[v]){
				if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
				else dfs2(v,1,k);
			}
		}
		else if(minn<=0){
			for(ll v=son[u];v;v=suf[v]){
				ll tmp=min(dp[v][0],dp[v][1]);
				if((dp[v][1]+w[v])<=tmp){
					dfs2(v,1,k);
					st[++top]=v;
				}
				else{
					if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
					else dfs2(v,1,k);
				}
			}
		}
		else{
			for(ll v=son[u];v;v=suf[v]){
				if(v==pos){
					dfs2(v,1,k);
					st[++top]=v;
				}
				else{
					if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
					else dfs2(v,1,k);
				}
			}
		}
	}
}
void print(ll u){
	pf("%lld %lld : %lld\n",fa[u],u,w[u]);
	for(ll v=son[u];v;v=suf[v]) print(v);
}
int main(){
	n=read();
	scanf("%s",s+1);
	fr(i,1,n) if(s[i]=='1') ck[i]=1;
	fr(i,2,n){
		ll u=read(),v=read();
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs0(1);
	cut(1);
//	pf("-----------------\n");
//	print(1);
	fr(k,1,n){
		dfs1(1,k);
		writeln(min(dp[1][0],dp[1][1]));
		if(dp[1][0]<=dp[1][1]) dfs2(1,0,k);
		else dfs2(1,1,k);
		fr(i,1,top){
			ll u=st[i],nxt;
			for(ll v=son[u];v;v=nxt){
				nxt=suf[v];
				del(u,v);
				ins(fa[u],v);
				w[v]+=w[u]+siz[u];
			}
			siz[fa[u]]+=siz[u]+w[u];
			ck[fa[u]]|=ck[u];
			del(fa[u],u);
		}
		top=0;
		cut(1);
//		pf("-----------------\n");
//		print(1);
	}
}

詳細信息

Test #1:

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

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: 5ms
memory: 8432kb

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: 9064kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...

output:

711
840
954
1055
1144
1219
1280
1344
1395
1443
1485
1527
1566
1605
1644
1682
1719
1755
1790
1823
1855
1887
1919
1950
1980
2009
2038
2066
2094
2122
2149
2176
2203
2228
2252
2275
2297
2319
2341
2363
2384
2404
2423
2441
2459
2477
2494
2511
2527
2542
2557
2571
2584
2596
2607
2618
2628
2638
2648
2658
266...

result:

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

Test #4:

score: 0
Wrong Answer
time: 47ms
memory: 8676kb

input:

5000
0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...

output:

890
1228
1488
1728
1898
2030
2118
2200
2263
2321
2374
2426
2473
2521
2567
2610
2650
2689
2728
2765
2800
2834
2867
2899
2930
2961
2990
3018
3046
3073
3098
3122
3145
3167
3189
3211
3232
3252
3271
3290
3309
3327
3345
3362
3378
3394
3410
3425
3439
3452
3464
3475
3485
3494
3503
3512
3521
3529
3536
3542
3...

result:

wrong answer 2nd numbers differ - expected: '1226', found: '1228'

Test #5:

score: 0
Wrong Answer
time: 33ms
memory: 8972kb

input:

5000
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...

output:

794
1040
1241
1428
1590
1695
1782
1864
1924
1985
2049
2096
2139
2179
2218
2257
2295
2332
2367
2401
2435
2469
2503
2536
2568
2600
2632
2663
2694
2724
2753
2781
2808
2834
2859
2883
2906
2929
2951
2973
2994
3014
3033
3052
3070
3087
3103
3118
3133
3147
3160
3172
3183
3193
3202
3210
3218
3225
3231
3236
3...

result:

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

Test #6:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30804
41826
49653
54274
55677
56398
56997
57451
57879
58279
58662
59039
59412
59779
60140
60500
60859
61216
61572
61927
62281
62634
62986
63338
63689
64039
64388
64736
65083
65429
65774
66118
66461
66803
67144
67484
67823
68161
68499
68836
69172
69507
69841
70175
70508
70840
71171
71501
71831
72160
...

result:


Test #7:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30644
41684
49594
54270
55626
56302
56868
57316
57744
58156
58547
58931
59312
59689
60058
60426
60794
61161
61527
61891
62254
62617
62979
63340
63699
64057
64414
64770
65125
65479
65832
66184
66536
66887
67237
67586
67934
68281
68627
68972
69316
69659
70001
70342
70682
71022
71361
71699
72036
72372
...

result:


Test #8:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

30736
41767
49608
54272
55596
56275
56843
57295
57728
58135
58520
58901
59277
59649
60016
60382
60747
61111
61473
61832
62191
62549
62907
63264
63620
63974
64327
64679
65030
65380
65729
66077
66424
66770
67115
67459
67803
68146
68488
68830
69171
69512
69852
70192
70531
70869
71206
71543
71879
72214
...

result:


Test #9:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12231
13894
15260
16410
17329
18081
18711
19256
19690
20089
20427
20733
21022
21290
21546
21787
22018
22241
22454
22661
22860
23061
23254
23446
23635
23820
24003
24183
24362
24539
24714
24888
25063
25234
25405
25578
25748
25918
26087
26255
26423
26590
26756
26922
27087
27252
27417
27581
27744
27907
...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15993
21898
26347
29982
32510
34166
35314
36110
36758
37292
37747
38156
38509
38843
39143
39426
39699
39955
40202
40438
40667
40891
41112
41326
41532
41734
41934
42127
42319
42508
42693
42877
43060
43242
43423
43603
43782
43959
44134
44308
44482
44655
44827
44998
45168
45336
45502
45667
45832
45997
...

result:


Test #11:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14608
18793
22574
25563
28423
30569
32349
33751
34896
35835
36643
37429
38141
38796
39413
40010
40582
41133
41667
42189
42698
43190
43663
44126
44578
45023
45462
45891
46314
46731
47129
47518
47901
48282
48658
49026
49390
49749
50102
50451
50793
51130
51463
51787
52107
52425
52735
53041
53342
53638
...

result:


Test #12:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12198
13850
15185
16296
17231
18010
18646
19184
19642
20058
20447
20788
21104
21404
21681
21951
22213
22468
22710
22946
23179
23409
23643
23872
24096
24314
24528
24741
24951
25163
25371
25578
25782
25986
26189
26391
26592
26794
26993
27192
27391
27590
27789
27987
28184
28381
28577
28772
28966
29160
...

result:


Test #13:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16072
21985
26409
30149
32614
34327
35542
36418
37106
37677
38181
38620
39015
39385
39714
40024
40327
40617
40886
41149
41404
41644
41872
42096
42316
42532
42746
42957
43167
43377
43584
43789
43991
44190
44389
44585
44779
44968
45155
45340
45525
45709
45893
46077
46261
46443
46624
46803
46980
47156
...

result:


Test #14:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14721
18966
22776
25919
28900
31013
32885
34366
35628
36650
37613
38406
39167
39798
40389
40944
41476
41981
42462
42922
43362
43793
44215
44621
45016
45397
45767
46122
46473
46812
47139
47452
47753
48045
48327
48605
48875
49140
49397
49647
49888
50125
50357
50588
50815
51041
51266
51488
51705
51922
...

result:


Test #15:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12121
13789
15149
18696
20498
22146
23629
25008
26299
27553
28764
29933
31084
32201
33299
34388
35467
36536
37600
38664
39722
40773
41821
42866
43909
44944
45976
47006
48040
49068
50096
51121
52147
53170
54193
55216
56238
57259
58279
59298
60316
61333
62350
63367
64383
65398
66413
67427
68441
69454
...

result:


Test #16:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

16192
22132
26632
30286
32897
34684
35864
36714
37404
37945
38416
38811
39170
39491
39791
40065
40330
40582
40828
41070
41301
41530
41755
41976
42195
42410
42619
42826
43033
43238
43441
43642
43842
44041
44240
44438
44634
44827
45019
45210
45399
45587
45774
45959
46141
46322
46500
46677
46852
47026
...

result:


Test #17:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

14705
18950
22799
25946
29000
31239
33115
34594
35922
36985
37968
38868
39685
40464
41223
41960
42675
43371
44054
44720
45377
46027
46667
47300
47925
48544
49159
49769
50374
50972
51568
52161
52749
53333
53915
54495
55073
55648
56221
56793
57361
57926
58487
59044
59599
60154
60708
61261
61811
62359
...

result:


Test #18:

score: 0
Time Limit Exceeded

input:

100000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12282
13921
15273
16418
17379
18142
18766
19303
19779
20175
20539
20881
21170
21437
21694
21943
22168
22384
22594
22806
23013
23213
23411
23607
23802
23993
24181
24366
24548
24729
24907
25085
25260
25435
25608
25780
25951
26121
26291
26461
26631
26800
26968
27135
27301
27466
27630
27794
27957
28119
...

result:


Test #19:

score: 4.16667
Accepted
time: 29ms
memory: 17112kb

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
43819
52537
59813
64875
68127
70393
71968
73193
74192
75014
75719
76318
76860
77365
77851
78311
78737
79145
79539
79915
80269
80600
80920
81234
81544
81849
82150
82449
82742
83032
83315
83596
83875
84148
84419
84688
84956
85219
85481
85741
85999
86257
86512
86767
87019
87270
87520
87768
88013
...

result:


Test #21:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

29187
37637
45119
51274
56769
61241
64744
67538
69782
71679
73274
74736
76106
77309
78437
79509
80532
81526
82494
83435
84349
85244
86125
86990
87837
88670
89491
90292
91079
91852
92614
93357
94094
94826
95551
96269
96977
97677
98372
99061
99739
100410
101072
101723
102364
102997
103620
104229
10482...

result:


Test #22:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

24124
27295
29803
36595
39967
43038
45875
48469
50942
53300
55574
57757
59896
62000
64066
66101
68118
70121
72102
74068
76026
77979
79919
81853
83785
85711
87632
89549
91467
93381
95291
97200
99108
101014
102920
104825
106730
108634
110538
112441
114344
116246
118147
120048
121948
123848
125747
1276...

result:


Test #23:

score: 0
Time Limit Exceeded

input:

200000
01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

32229
44031
52843
60297
65336
68505
70757
72350
73551
74473
75267
75929
76521
77053
77548
77997
78425
78842
79234
79611
79976
80328
80670
81010
81342
81668
81984
82296
82603
82902
83197
83491
83782
84073
84360
84646
84930
85212
85492
85770
86045
86319
86592
86862
87128
87391
87650
87908
88165
88420
...

result:


Test #24:

score: 4.16667
Accepted
time: 125ms
memory: 24444kb

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:

ok 200000 numbers