QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448620#8806. Summer Drivingmiaomiaomiaowu1 2041ms120308kbC++204.0kb2024-06-19 20:07:502024-06-19 20:07:50

Judging History

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

  • [2024-06-19 20:07:50]
  • 评测
  • 测评结果:1
  • 用时:2041ms
  • 内存:120308kb
  • [2024-06-19 20:07:50]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<int,int>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
	char c;x=0;bool f=0;
	for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
const int N=3e5+5;
vector<int>g[N],qaq[N],dt[N];
int n,rt,A,B,de[N],anc[N],F[N][20],mxde[N],_mxde[N],K[N],Mn[N],Mmn[N],_can[N],dfn[N],fn,siz[N],ccc[N];
bool can[N],f[N],gg[N],cc[N];
inline void init(int u,int fa){
	de[u]=de[fa]+1,mxde[u]=_mxde[u]=de[u];
	F[u][0]=fa,dfn[u]=++fn,siz[u]=1;
	for(int i=1;i<20;i++)
		F[u][i]=F[F[u][i-1]][i-1];
	for(int v:g[u]){
		if(v==fa)continue;
		init(v,u),siz[u]+=siz[v];
		if(mxde[v]>mxde[u]){
			_mxde[u]=mxde[u],mxde[u]=mxde[v];
		}
		else _mxde[u]=max(_mxde[u],mxde[v]);
	}
}
struct SGT{
	int tag[N<<2];
	inline int ls(int u){return u<<1;}
	inline int rs(int u){return u<<1|1;}
	inline void clear(){
		memset(tag,-1,sizeof tag);
	}
	inline void pd(int u){
		if(tag[u]==-1)return;
		tag[ls(u)]=tag[rs(u)]=tag[u];
		tag[u]=-1;
	}
	inline void upd(int u,int l,int r,int L,int R,int x){
		if(l>=L&&r<=R)return tag[u]=x,void();
		int mid=l+r>>1;pd(u);
		if(mid>=L)upd(ls(u),l,mid,L,R,x);
		if(mid<R)upd(rs(u),mid+1,r,L,R,x);
	}
	inline int qry(int u,int l,int r,int p){
		if(l==r)return tag[u];
		int mid=l+r>>1;pd(u);
		return mid>=p?qry(ls(u),l,mid,p):qry(rs(u),mid+1,r,p);
	}
}sgt;
inline void dfs(int u,int fa){
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
	if(mxde[u]-de[u]<A)f[u]=can[u];
	if(u!=rt){
		if(mxde[fa]==mxde[u]){
			if(_mxde[fa]-de[fa]<A)gg[u]=cc[u];
		}
		else{
			if(mxde[fa]-de[fa]<A)gg[u]=cc[u];
		}
	}
	// if(u==3)cout<<"! "<<gg[u]<<endl;
	if(qaq[fa].size()>1)gg[u]=1;
	else if(qaq[fa].size()==1&&qaq[fa][0]!=u)gg[u]=1;
	// if(u==3)cout<<"! "<<gg[u]<<endl;
	// if(gg[u])sgt.upd(1,1,n,dfn[u],dfn[u],1);
	// else sgt.upd(1,1,n,dfn[u],dfn[u]+siz[u]-1,0);
	if(F[anc[u]][0])for(int y:dt[u]){
		// if(f[y]&&sgt.qry(1,1,n,dfn[y])){
		if(f[y]){
			int v=y,flag=1;
			while(1){
				if(!gg[v]){flag=0;break;}
				if(v==u)break;
				v=F[v][0];
			}
			if(!flag)continue;
			f[F[anc[u]][0]]=1;
			qaq[F[anc[u]][0]].push_back(anc[u]);
		}
	}
}
inline void QWQ(int x){
	for(int i=1;i<=n;i++){
		if(mxde[i]-de[i]<A)can[i]=(_can[i]>=x);
		else can[i]=0;
		cc[i]=0;
		if(i!=rt){
			if(K[F[i][0]]!=i)cc[i]=(Mn[F[i][0]]>=x);
			else cc[i]=(Mmn[F[i][0]]>=x);
		}
	}
	memset(f,0,sizeof f);
	memset(gg,0,sizeof gg);
	for(int i=1;i<=n;i++)qaq[i].clear();
	sgt.clear(),dfs(rt,0);
}
int main(){
	in(n),in(rt),in(A),in(B);
	if(B>=A)return puts("1"),0;
	for(int i=1,u,v;i<n;i++){
		in(u),in(v);
		g[u].push_back(v),g[v].push_back(u);
	}
	init(rt,0);
	for(int i=1;i<=n;i++){
		int u=i;
		for(int j=0;j<20;j++){
			if(A-B>>j&1)u=F[u][j];
		}
		anc[i]=u;
	}
	for(int i=1;i<=n;i++){
		int u=i;
		for(int j=0;j<20;j++){
			if(B-1>>j&1)u=F[u][j];
		}
		if(u)dt[u].push_back(i);
	}
	for(int i=1;i<=n;i++){
		_can[i]=Mn[i]=Mmn[i]=i;
		ccc[i]=i;
	}
	for(int i=1;i<=n;i++){
		int u=i;
		for(int j=1;j<=B;j++){
			u=F[u][0];
			if(!u)break;
			_can[u]=min(_can[u],i);
		}
	}
	for(int i=1;i<=n;i++){
		int u=i;
		for(int j=1;j<B;j++){
			u=F[u][0];
			if(!u)break;
			ccc[u]=min(ccc[u],i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int v:g[i]){
			if(v==F[i][0])continue;
			if(ccc[v]<Mn[i]){
				Mmn[i]=Mn[i],Mn[i]=ccc[v];
				K[i]=v;
			}
			else Mmn[i]=min(Mmn[i],ccc[v]);
		}
	}
	// cout<<Mmn[7]<<endl;
	// QWQ(3);
	// for(int i=1;i<=n;i++){
		// cout<<i<<' '<<can[i]<<' '<<cc[i]<<' '<<f[i]<<' '<<gg[i]<<endl;
	// }
	// return 0;
	int l=1,r=n,res;
	while(l<=r){
		int mid=l+r>>1;
		QWQ(mid);
		if(f[rt])res=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<res<<endl;
	return 0;
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 0ms
memory: 3608kb

input:

300000 110732 1 1
54285 169439
18968 45543
130988 134682
162292 70081
212010 121474
128140 292466
209394 38279
91706 225569
67647 188578
265505 84279
161782 137098
27472 221980
284973 79104
230628 268631
69945 205947
153720 168119
230161 32244
138981 44376
165008 136947
125742 123375
209131 122038
8...

output:

1

result:

ok single line: '1'

Test #2:

score: 1
Accepted
time: 2ms
memory: 3584kb

input:

300000 123141 300000 300000
35459 173656
6934 241069
183095 87288
269195 16957
19492 242321
24470 81747
25697 172188
171424 220229
160473 69937
172168 99268
220664 39397
8212 2407
46718 94855
279515 295195
205222 167038
185958 111515
172553 45818
141322 214355
61335 64490
183502 105408
234540 245525...

output:

1

result:

ok single line: '1'

Test #3:

score: 1
Accepted
time: 2ms
memory: 3548kb

input:

298765 30225 2 3
265195 252069
113697 255482
227617 218688
279488 136408
179394 139291
86777 211320
255097 13136
68860 173342
178971 175020
278041 278319
285893 289677
194438 44163
56223 283058
110392 123602
20729 89517
152134 176747
121481 243463
297305 139297
244189 117068
181785 39468
154302 1860...

output:

1

result:

ok single line: '1'

Test #4:

score: 1
Accepted
time: 2ms
memory: 3592kb

input:

299987 224030 2 2
177674 20066
211112 287348
150440 136779
131528 209570
208840 36580
3395 152219
89118 44403
120439 274280
267578 80200
17796 257578
229408 211795
122773 147368
139779 842
94469 299092
211457 29057
9040 117449
216268 88141
40844 98163
183412 221031
230933 237086
147633 135982
282224...

output:

1

result:

ok single line: '1'

Test #5:

score: 1
Accepted
time: 2ms
memory: 3720kb

input:

2 1 1 2
2 1

output:

1

result:

ok single line: '1'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 2041ms
memory: 120308kb

input:

300000 226344 300 9
32176 183340
249597 14851
145160 92372
30564 242505
1140 169463
279867 14442
266653 32911
168819 26009
138049 133460
5327 103921
262703 112512
204338 84304
98144 9089
98632 238236
79093 101104
50327 237759
61236 275195
241153 116369
86842 272794
25675 121176
110170 225753
199931 ...

output:

7

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #18:

score: 5
Accepted
time: 3ms
memory: 9028kb

input:

300 42 3 2
114 268
132 105
187 17
191 127
14 62
162 126
39 143
72 159
199 184
295 138
71 277
293 103
288 54
231 196
57 220
110 117
38 136
295 258
41 76
291 8
59 131
161 278
244 233
81 76
12 236
21 240
228 262
255 159
236 60
277 33
29 123
170 290
89 154
220 139
193 81
31 53
163 77
148 274
181 76
15 2...

output:

83

result:

ok single line: '83'

Test #19:

score: 0
Wrong Answer
time: 5ms
memory: 9124kb

input:

300 178 3 2
277 106
123 105
235 290
273 34
300 180
43 55
239 74
19 138
110 201
295 18
207 97
238 177
114 24
195 219
154 186
151 294
143 291
47 293
33 99
2 46
101 39
109 240
15 256
43 121
205 261
267 257
81 167
82 23
300 182
13 46
195 221
163 17
109 93
144 23
110 17
153 129
91 243
281 74
135 72
145 1...

output:

81

result:

wrong answer 1st lines differ - expected: '4', found: '81'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #49:

score: 0
Wrong Answer
time: 182ms
memory: 33000kb

input:

100000 20749 3 2
89778 51257
2293 75317
20142 42260
55350 69024
2419 90402
2248 71914
60607 94307
33933 57799
79884 93934
9788 53542
18109 28742
7700 93763
12102 78825
34580 61577
84344 12887
63610 12371
30988 75638
47533 66209
95296 22495
12638 545
36347 57495
41813 49592
60342 1881
38899 62345
524...

output:

54408

result:

wrong answer 1st lines differ - expected: '43056', found: '54408'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%