QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201431#5157. High-quality TreeBoulevardDust#WA 487ms33384kbC++202.2kb2023-10-05 14:18:452023-10-05 14:18:46

Judging History

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

  • [2023-10-05 14:18:46]
  • 评测
  • 测评结果:WA
  • 用时:487ms
  • 内存:33384kb
  • [2023-10-05 14:18:45]
  • 提交

answer

#include<bits/stdc++.h>
#define N 300005
#define re 
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
	re char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
int head[N],to[N<<1],nxt[N<<1],cnt1;
inline void adde(int x,int y){to[++cnt1]=y;nxt[cnt1]=head[x];head[x]=cnt1;}
int fa[N],dep[N],totid,L[N],R[N],dfn[N];
int Lson[N],Rson[N],cnt[N];
void dfs(int x,int f){
	fa[x]=f;dep[x]=dep[f]+1;
	L[x]=++totid;dfn[totid]=x;
	for(re int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f)continue;
		if(Lson[x]==0)Lson[x]=y;
		else Rson[x]=y;
		cnt[x]++;
		dfs(y,x);
	}
	R[x]=totid;
}
int tree[N<<2];
void Build(int l,int r,int p){
	if(l==r){
		tree[p]=dep[dfn[l]];
		return;
	}
	int mid=(l+r)>>1;
	Build(l,mid,p<<1);
	Build(mid+1,r,p<<1|1);
	tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int query(int l,int r,int L,int R,int p){
	if(l==L&&r==R)return tree[p];
	int mid=(l+r)>>1;
	if(R<=mid)return query(l,mid,L,R,p<<1);
	else if(L>mid)return query(mid+1,r,L,R,p<<1|1);
	else return max(query(l,mid,L,mid,p<<1),query(mid+1,r,mid+1,R,p<<1|1));
}
void update(int l,int r,int x,int p){
	if(l==r){tree[p]=0;return;}
	int mid=(l+r)>>1;
	if(x<=mid)update(l,mid,x,p<<1);
	else update(mid+1,r,x,p<<1|1);
	tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int a[N];
bool cmp(int x,int y){return dep[x]>dep[y];}
bool in(int x,int y){return L[x]<=L[y]&&R[x]>=L[y];}
bool check(int x){
	int t=fa[x];
	while(t){
		int d1=dep[t],d2=dep[t];
		if(Lson[t]!=0)d1=max(d1,query(1,n,L[Lson[t]],R[Lson[t]],1));
		if(Rson[t]!=0)d2=max(d2,query(1,n,L[Rson[t]],R[Rson[t]],1));
		if(dep[x]>min(d1,d2)+1)return 0;
		t=fa[t];
	}
	return 1;
}
int ans;
struct node{
	int x,d;
	bool operator<(const node&res)const{return d>res.d;}
};
priority_queue<node>Q;
void Del(int x){
	update(1,n,L[x],1);
	ans++;
	if(x==1)return;
	x=fa[x];cnt[x]--;
	if(cnt[x]==0)Q.push((node){x,dep[x]});
}
int main(){
	Rd(n);
	for(re int i=1;i<n;i++){
		int x,y;
		Rd(x),Rd(y);
		adde(x,y);
		adde(y,x);
	}
	dfs(1,0);
	Build(1,n,1);
	for(re int i=1;i<=n;i++)
		if(cnt[i]==0)Q.push((node){i,dep[i]});
	while(!Q.empty()){
		int x=Q.top().x;Q.pop();
		if(!check(x))Del(x);
	}
	printf("%d\n",ans);
	
	
	
	return 0;
} 

詳細信息

Test #1:

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

input:

6
1 2
1 3
3 4
3 5
5 6

output:

1

result:

ok single line: '1'

Test #2:

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

input:

12
1 2
2 3
3 4
3 5
1 6
6 7
7 8
7 9
9 10
6 11
11 12

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 253ms
memory: 25944kb

input:

200000
167246 158246
40931 40296
178588 27974
35171 899
4204 163250
101422 9230
55420 93371
16012 140142
28866 154497
33519 180725
50361 52348
46923 175364
126599 169575
15138 34958
164256 64770
63123 130169
154172 168301
127476 54744
199964 81879
173765 69220
178225 73653
59861 46415
138112 17507
8...

output:

199998

result:

ok single line: '199998'

Test #4:

score: 0
Accepted
time: 92ms
memory: 33384kb

input:

200000
144434 24107
75087 108465
38670 156657
31235 30143
40544 44213
51188 21788
170574 164351
14169 155909
120876 119956
196361 140453
197958 142813
23944 62568
12098 71652
162226 122184
123783 86178
70076 115586
74439 94246
83296 36713
182500 16937
174946 154091
97484 194764
179943 61793
114439 1...

output:

199998

result:

ok single line: '199998'

Test #5:

score: 0
Accepted
time: 487ms
memory: 20348kb

input:

200000
42469 8516
3910 143673
129125 150433
170053 160404
147325 66173
130784 195620
183508 43943
90940 88012
187183 803
139576 36677
190280 71191
107959 177664
14308 20402
93449 130555
80315 75413
178265 104526
4428 8875
151397 91172
181321 47276
105060 81973
196326 19584
44364 56143
187070 195424
...

output:

199998

result:

ok single line: '199998'

Test #6:

score: 0
Accepted
time: 251ms
memory: 19904kb

input:

131071
94531 87688
119005 53065
70725 126770
61026 82294
114384 270
98205 38915
61461 14652
123122 36872
37639 52311
17774 89648
79899 59785
6033 52465
15449 93250
43849 18174
2665 82543
26740 15199
71645 14339
45549 119270
22896 70677
126250 23614
5796 85715
92715 25280
119740 8911
17923 5547
47703...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

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

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 107ms
memory: 16108kb

input:

75026
12155 64806
40053 74785
70103 1220
72989 33966
74199 66365
52024 24358
54545 52118
52572 28566
68873 41146
10161 67848
41221 63589
72291 44013
51515 14784
12150 33009
3919 23413
61773 13741
21172 17759
27774 65766
58702 13619
11690 19263
45469 30662
33296 45184
51641 13235
11413 52734
74437 57...

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 7ms
memory: 14400kb

input:

10947
7184 5103
1433 10766
3794 8428
1438 8926
2493 7796
6753 7135
3304 4497
9148 8680
4013 2259
3067 8641
2809 9523
9557 2452
8392 3411
1121 6418
5150 133
8893 3701
7864 3044
7152 705
3856 5325
10943 4760
9792 7866
6959 6282
1120 7627
2952 9675
10407 9119
2489 1131
907 4948
4175 3572
4178 337
226 7...

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 2ms
memory: 14400kb

input:

8375
5605 5852
7762 3219
1669 4378
341 6410
1502 1920
706 8356
5088 5723
1326 6305
2433 5341
5185 948
7639 5745
6173 7572
4736 7204
8081 3452
2414 6798
156 7332
6627 2209
876 5078
2666 292
5041 7782
7118 807
6897 5220
5865 1273
6546 1506
4306 7980
1119 6488
4795 5942
6219 7729
8119 1572
4027 4817
46...

output:

701

result:

ok single line: '701'

Test #11:

score: 0
Accepted
time: 17ms
memory: 14828kb

input:

19450
13860 10518
15222 9423
8628 4061
13172 14144
10621 1876
14867 11492
5902 19300
11313 2895
2777 6935
6948 18381
13897 14220
11979 19134
5771 10820
19025 16787
8909 7140
10163 19125
4204 5969
8802 3293
11379 17457
4788 6749
14771 10567
5201 18207
3410 7595
12521 4698
19184 15244
10662 7902
16998...

output:

732

result:

ok single line: '732'

Test #12:

score: 0
Accepted
time: 173ms
memory: 28188kb

input:

199999
42470 186792
84838 99410
115027 161613
35565 77810
72472 47859
180671 162382
32852 67468
75811 198709
124926 126090
54877 26903
165267 13544
8081 157453
152632 92738
145016 76659
74572 183100
116308 42324
140949 129632
170934 122224
10244 34160
88908 198457
124270 136554
190537 124534
137981 ...

output:

199994

result:

ok single line: '199994'

Test #13:

score: 0
Accepted
time: 187ms
memory: 27360kb

input:

199999
32647 44026
42853 57810
175394 58242
95892 8293
2439 15285
112251 57100
187050 83100
112980 29377
157012 134211
135596 33147
85472 59785
139169 125631
153085 165140
82629 73365
25158 16327
191064 93990
123231 32916
130815 20323
129599 77035
144632 98686
67473 3578
172156 98862
21894 195995
16...

output:

199994

result:

ok single line: '199994'

Test #14:

score: 0
Accepted
time: 189ms
memory: 27848kb

input:

199999
37321 183353
197048 89193
114486 34848
82027 85518
62564 117961
17663 28259
91838 124561
188988 46866
156756 75225
105968 183481
118948 67500
75409 123761
107128 52670
171953 102720
62773 165219
194620 173567
31552 88489
97494 15048
189108 36762
11031 1741
64889 67129
158657 157875
191291 359...

output:

199994

result:

ok single line: '199994'

Test #15:

score: 0
Accepted
time: 449ms
memory: 20316kb

input:

200000
196903 77452
27188 55527
102207 165320
134712 55341
162994 81141
85731 30299
75243 18518
23639 84881
197033 143822
120492 51146
46281 145275
99830 195228
185002 53761
54098 31449
60141 191308
193012 177578
67355 11089
66265 166383
34969 194717
175543 128704
40124 39801
196897 185270
34468 798...

output:

5234

result:

ok single line: '5234'

Test #16:

score: -100
Wrong Answer
time: 300ms
memory: 21692kb

input:

200000
164768 68803
153609 72233
28630 173584
188468 26064
147938 153547
106394 130342
153098 185806
157156 94496
141556 40929
79526 192838
66642 19962
39033 118375
82614 132264
116065 11968
2498 145405
27683 44830
188353 171809
40025 55356
95932 76953
71476 192804
36377 176226
150808 112053
62032 2...

output:

83156

result:

wrong answer 1st lines differ - expected: '87285', found: '83156'