oj.uz

Submission #1056269

# Submission time Handle Problem Language Result Execution time Memory
1056269 2024-08-13T08:33:02 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 1156 ms 679860 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
const int N=300005;
int n,r,a,b,dep[N],p[N],q[N],L[N],pA[N],subA[N];
int sz[N],in[N],inv[N],out[N],C,ctop[N];
vector<int> dp[N],dp2[N];
int dp3[N][15],dp4[N][15];
vector<int> g[N],c[N],dL[N];
vector<int> dA[N],idxsubA[N];
vector<int> up[N],invup[N];
vector<pii> ev[N];
struct SEG{
	int T[2*N];
	void init(int nd,int l,int r){
		T[nd]=1e9;
		if(l==r) return;
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		init(ln,l,m); init(rn,m+1,r);
	}
	void upd(int nd,int l,int r,int x,int v){
		T[nd]=min(T[nd],v);
		if(l==r) return;
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		if(x<=m) upd(ln,l,m,x,v);
		else upd(rn,m+1,r,x,v);
	}
	int qry(int nd,int l,int r,int s,int e){
		if(r<s||e<l) return 1e9;
		if(s<=l&&r<=e) return T[nd];
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		return min(qry(ln,l,m,s,e),qry(rn,m+1,r,s,e));
	}
}T[2];
void dfs0(int u){
	L[dep[u]]=u;
	dL[dep[u]].push_back(u);
	if(dep[u]>=a){
		pA[u]=L[dep[u]-a];
		subA[u]=L[dep[u]-a+1];
		idxsubA[subA[u]].push_back(dA[pA[u]].size());
		dA[pA[u]].push_back(u);
	}
	sz[u]=1;
	for(int v: g[u]) if(p[u]!=v){
		dep[v]=dep[u]+1;
		p[v]=u;
		c[u].push_back(v);
		dfs0(v);
		sz[u]+=sz[v];
	}
}
void dfsH(int u,int t){
	in[u]=++C;
	inv[in[u]]=u;
	ctop[u]=t;
	int idx=0;
	for(int v: c[u]){
		q[v]=++idx;
		if(v==c[u][0]) dfsH(v,t);
		else dfsH(v,v);
	}
	out[u]=C;
}
struct ErasableSet{
	priority_queue<int> pq1,pq2;
	void insert(int x){
		pq1.push(x);
	}
	void erase(int x){
		pq2.push(x);
	}
	int top(){
		while(pq2.size()&&pq1.top()==pq2.top()){
			pq1.pop();
			pq2.pop();
		}
		return pq1.top();
	}
	int size(){
		return pq1.size()-pq2.size();
	}
}dp2C[N],dp3D[N][15];
int dfs1(int u,int d){
	int &ret=dp3[u][d];
	if(ret) return ret;
	ret=dp[u][0];
	if(d>=1) for(int v: c[u]) ret=min(ret,dfs1(v,d-1));
	return ret;
}
int dfs2(int u,int d){
	int &ret=dp4[u][d];
	if(ret) return ret;
	ret=u;
	if(d>=1) for(int v: c[u]) ret=min(ret,dfs2(v,d-1));
	return ret;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>r>>a>>b;
	if(a<=b){
		cout<<"1\n";
		return 0;
	}
	for(int u,v,i=1;i<n;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs0(r);
	for(int u=1;u<=n;u++){
		for(int &v: c[u]) if(sz[v]>sz[c[u][0]]) swap(v,c[u][0]);
	}
	dfsH(r,r);
	for(int i=1;i<=n;i++){
		dp[i].resize(c[i].size()+1);
		dp2[i].resize(dA[i].size());
	}
	for(int i=1;i<=n;i++){
		int u=i;
		while(u){
			if(dep[i]-dep[u]>b) break;
			up[i].push_back(u);
			invup[u].push_back(i);
			if(dep[u]-a+b-(dep[i]-dep[u])>=0) ev[dep[u]-a+b-(dep[i]-dep[u])].push_back({i,u});
			u=p[ctop[u]];
		}
	}
	T[0].init(1,1,n);
	T[1].init(1,1,n);
	for(int D=n;D>=0;D--){
		for(int u: dL[D]){
			for(int i=0;i<(int)dA[u].size();i++){
				int v=dA[u][i];
				int val=dfs1(v,b);
				{
					int w=v,e=0;
					while(w){
						if(dep[v]-dep[w]>b) break;
						int ww=ctop[w];
						if(dep[v]-dep[ww]>b){
							ww=inv[in[ww]+(dep[v]-dep[ww]-b)];
							assert(dep[v]-dep[ww]==b);
						}
						if(in[ww]<=in[w]-1) val=min(val,T[0].qry(1,1,n,in[ww],in[w]-1));
						val=min(val,dp[w][e]);
						e=q[ww];
						w=p[ww];
					}
				}
				{
					int w=v,e=0,d=0;
					while(d<b){
						e=q[w];
						w=p[w];
						d++;
						if(d<b){
							if((int)dp3D[w][b-d].size()!=(int)c[w].size()){
								for(int j=0;j<(int)c[w].size();j++) dp3D[w][b-d].insert(-dfs1(c[w][j],b-d-1));
							}
							if((int)c[w].size()>1){
								dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
								val=min(val,-dp3D[w][b-d].top());
								dp3D[w][b-d].insert(-dfs1(c[w][e-1],b-d-1));
							}
						}
					}
				}
				dp2[u][i]=val;
				dp2C[u].insert(dp2[u][i]);
			}
			for(int k=0;k<=(int)c[u].size();k++){
				int &ret=dp[u][k];
				if(dA[u].empty()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
					if(k&&idxsubA[c[u][k-1]].empty()) ret=dp[u][0];
					else{
						ret=u;
						for(int i=0;i<(int)c[u].size();i++) if(i+1!=k) ret=min(ret,dfs2(c[u][i],b-1));
					}
				} else{
					if(k){
						for(int i: idxsubA[c[u][k-1]]){
							dp2C[u].erase(dp2[u][i]);
						}
					}
					ret=dp2C[u].top();
					if(k){
						for(int i: idxsubA[c[u][k-1]]) dp2C[u].insert(dp2[u][i]);
					}
				}
			}
			if(c[u].size()) T[0].upd(1,1,n,in[u],dp[u][1]);
		}
	}
	cout<<dp[r][0];
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 377936 KB Output is correct
2 Correct 48 ms 378116 KB Output is correct
3 Correct 47 ms 378160 KB Output is correct
4 Correct 48 ms 378128 KB Output is correct
5 Correct 54 ms 377936 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 615848 KB Output is correct
2 Correct 1156 ms 639848 KB Output is correct
3 Incorrect 934 ms 679860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 388552 KB Output is correct
2 Correct 51 ms 388312 KB Output is correct
3 Correct 53 ms 388368 KB Output is correct
4 Correct 56 ms 388432 KB Output is correct
5 Correct 60 ms 388432 KB Output is correct
6 Correct 53 ms 388288 KB Output is correct
7 Correct 56 ms 388552 KB Output is correct
8 Correct 51 ms 386440 KB Output is correct
9 Correct 53 ms 377956 KB Output is correct
10 Correct 52 ms 388508 KB Output is correct
11 Correct 58 ms 388720 KB Output is correct
12 Correct 60 ms 388272 KB Output is correct
13 Correct 51 ms 388440 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 388552 KB Output is correct
2 Correct 51 ms 388312 KB Output is correct
3 Correct 53 ms 388368 KB Output is correct
4 Correct 56 ms 388432 KB Output is correct
5 Correct 60 ms 388432 KB Output is correct
6 Correct 53 ms 388288 KB Output is correct
7 Correct 56 ms 388552 KB Output is correct
8 Correct 51 ms 386440 KB Output is correct
9 Correct 53 ms 377956 KB Output is correct
10 Correct 52 ms 388508 KB Output is correct
11 Correct 58 ms 388720 KB Output is correct
12 Correct 60 ms 388272 KB Output is correct
13 Correct 51 ms 388440 KB Output is correct
14 Correct 55 ms 389212 KB Output is correct
15 Correct 64 ms 389180 KB Output is correct
16 Correct 53 ms 389168 KB Output is correct
17 Correct 64 ms 389336 KB Output is correct
18 Correct 54 ms 389168 KB Output is correct
19 Correct 62 ms 389140 KB Output is correct
20 Correct 56 ms 389480 KB Output is correct
21 Correct 51 ms 386676 KB Output is correct
22 Correct 49 ms 378116 KB Output is correct
23 Correct 62 ms 389968 KB Output is correct
24 Correct 62 ms 389448 KB Output is correct
25 Incorrect 70 ms 390484 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 422724 KB Output is correct
2 Correct 234 ms 423796 KB Output is correct
3 Correct 188 ms 422264 KB Output is correct
4 Correct 192 ms 422992 KB Output is correct
5 Correct 172 ms 419696 KB Output is correct
6 Correct 223 ms 420528 KB Output is correct
7 Correct 223 ms 426324 KB Output is correct
8 Correct 129 ms 408272 KB Output is correct
9 Correct 282 ms 433352 KB Output is correct
10 Correct 247 ms 425572 KB Output is correct
11 Correct 160 ms 406864 KB Output is correct
12 Correct 149 ms 409768 KB Output is correct
13 Correct 57 ms 378084 KB Output is correct
14 Correct 56 ms 377936 KB Output is correct
15 Correct 282 ms 428372 KB Output is correct
16 Correct 158 ms 418752 KB Output is correct
17 Correct 122 ms 418896 KB Output is correct
18 Correct 128 ms 418884 KB Output is correct
19 Correct 318 ms 466772 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 388552 KB Output is correct
2 Correct 51 ms 388312 KB Output is correct
3 Correct 53 ms 388368 KB Output is correct
4 Correct 56 ms 388432 KB Output is correct
5 Correct 60 ms 388432 KB Output is correct
6 Correct 53 ms 388288 KB Output is correct
7 Correct 56 ms 388552 KB Output is correct
8 Correct 51 ms 386440 KB Output is correct
9 Correct 53 ms 377956 KB Output is correct
10 Correct 52 ms 388508 KB Output is correct
11 Correct 58 ms 388720 KB Output is correct
12 Correct 60 ms 388272 KB Output is correct
13 Correct 51 ms 388440 KB Output is correct
14 Correct 55 ms 389212 KB Output is correct
15 Correct 64 ms 389180 KB Output is correct
16 Correct 53 ms 389168 KB Output is correct
17 Correct 64 ms 389336 KB Output is correct
18 Correct 54 ms 389168 KB Output is correct
19 Correct 62 ms 389140 KB Output is correct
20 Correct 56 ms 389480 KB Output is correct
21 Correct 51 ms 386676 KB Output is correct
22 Correct 49 ms 378116 KB Output is correct
23 Correct 62 ms 389968 KB Output is correct
24 Correct 62 ms 389448 KB Output is correct
25 Incorrect 70 ms 390484 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 377936 KB Output is correct
2 Correct 48 ms 378116 KB Output is correct
3 Correct 47 ms 378160 KB Output is correct
4 Correct 48 ms 378128 KB Output is correct
5 Correct 54 ms 377936 KB Output is correct
6 Correct 1034 ms 615848 KB Output is correct
7 Correct 1156 ms 639848 KB Output is correct
8 Incorrect 934 ms 679860 KB Output isn't correct
9 Halted 0 ms 0 KB -