oj.uz

Submission #1056334

# Submission time Handle Problem Language Result Execution time Memory
1056334 2024-08-13T08:54:55 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 1999 ms 1048576 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;
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;
			if(u!=i){
				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.init(1,1,n);
	for(int D=n;D>=0;D--){
		for(auto [u,v]: ev[D]) T.upd(1,1,n,in[u],dp[v][0]);
		for(int u: dL[D]){
			for(int i=0;i<(int)dA[u].size();i++){
				int v=dA[u][i];
				int val=1e9;
				{
					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.qry(1,1,n,in[ww],in[w]-1));
						val=min(val,dp[w][e]);
						while(1){
							int d=dep[v]-dep[w];
							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(d<b){
								if(e) dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
								if(dp3D[w][b-d].size()){
									val=min(val,-dp3D[w][b-d].top());
								}
								if(e) dp3D[w][b-d].insert(-dfs1(c[w][e-1],b-d-1));
							}
							if(w==ww) break;
							e=q[w];
							w=p[w];
						}
						e=q[ww];
						w=p[ww];
					}
				}
				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.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 55 ms 377940 KB Output is correct
2 Correct 113 ms 371488 KB Output is correct
3 Correct 116 ms 371536 KB Output is correct
4 Correct 117 ms 371396 KB Output is correct
5 Correct 155 ms 371284 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 677720 KB Output is correct
2 Correct 1676 ms 721228 KB Output is correct
3 Runtime error 1999 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 378128 KB Output is correct
2 Correct 109 ms 378180 KB Output is correct
3 Correct 114 ms 378096 KB Output is correct
4 Correct 104 ms 378144 KB Output is correct
5 Correct 103 ms 378272 KB Output is correct
6 Correct 120 ms 378212 KB Output is correct
7 Correct 101 ms 378100 KB Output is correct
8 Correct 109 ms 384220 KB Output is correct
9 Correct 106 ms 377940 KB Output is correct
10 Correct 51 ms 386388 KB Output is correct
11 Correct 51 ms 386684 KB Output is correct
12 Correct 59 ms 386388 KB Output is correct
13 Correct 52 ms 386348 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 378128 KB Output is correct
2 Correct 109 ms 378180 KB Output is correct
3 Correct 114 ms 378096 KB Output is correct
4 Correct 104 ms 378144 KB Output is correct
5 Correct 103 ms 378272 KB Output is correct
6 Correct 120 ms 378212 KB Output is correct
7 Correct 101 ms 378100 KB Output is correct
8 Correct 109 ms 384220 KB Output is correct
9 Correct 106 ms 377940 KB Output is correct
10 Correct 51 ms 386388 KB Output is correct
11 Correct 51 ms 386684 KB Output is correct
12 Correct 59 ms 386388 KB Output is correct
13 Correct 52 ms 386348 KB Output is correct
14 Correct 58 ms 387156 KB Output is correct
15 Correct 67 ms 387240 KB Output is correct
16 Correct 54 ms 387052 KB Output is correct
17 Correct 58 ms 387276 KB Output is correct
18 Correct 55 ms 387156 KB Output is correct
19 Correct 54 ms 387156 KB Output is correct
20 Correct 62 ms 387244 KB Output is correct
21 Correct 60 ms 384536 KB Output is correct
22 Correct 50 ms 377940 KB Output is correct
23 Correct 64 ms 388556 KB Output is correct
24 Correct 56 ms 387576 KB Output is correct
25 Incorrect 66 ms 389032 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 217 ms 419672 KB Output is correct
2 Correct 265 ms 421056 KB Output is correct
3 Correct 281 ms 419216 KB Output is correct
4 Correct 260 ms 420356 KB Output is correct
5 Correct 189 ms 415692 KB Output is correct
6 Correct 211 ms 417068 KB Output is correct
7 Correct 304 ms 424832 KB Output is correct
8 Correct 131 ms 402836 KB Output is correct
9 Correct 415 ms 434488 KB Output is correct
10 Correct 283 ms 423836 KB Output is correct
11 Correct 145 ms 401860 KB Output is correct
12 Correct 145 ms 403384 KB Output is correct
13 Correct 53 ms 378136 KB Output is correct
14 Correct 55 ms 378172 KB Output is correct
15 Correct 336 ms 429544 KB Output is correct
16 Correct 157 ms 413744 KB Output is correct
17 Correct 137 ms 413524 KB Output is correct
18 Correct 143 ms 413528 KB Output is correct
19 Correct 423 ms 486232 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 378128 KB Output is correct
2 Correct 109 ms 378180 KB Output is correct
3 Correct 114 ms 378096 KB Output is correct
4 Correct 104 ms 378144 KB Output is correct
5 Correct 103 ms 378272 KB Output is correct
6 Correct 120 ms 378212 KB Output is correct
7 Correct 101 ms 378100 KB Output is correct
8 Correct 109 ms 384220 KB Output is correct
9 Correct 106 ms 377940 KB Output is correct
10 Correct 51 ms 386388 KB Output is correct
11 Correct 51 ms 386684 KB Output is correct
12 Correct 59 ms 386388 KB Output is correct
13 Correct 52 ms 386348 KB Output is correct
14 Correct 58 ms 387156 KB Output is correct
15 Correct 67 ms 387240 KB Output is correct
16 Correct 54 ms 387052 KB Output is correct
17 Correct 58 ms 387276 KB Output is correct
18 Correct 55 ms 387156 KB Output is correct
19 Correct 54 ms 387156 KB Output is correct
20 Correct 62 ms 387244 KB Output is correct
21 Correct 60 ms 384536 KB Output is correct
22 Correct 50 ms 377940 KB Output is correct
23 Correct 64 ms 388556 KB Output is correct
24 Correct 56 ms 387576 KB Output is correct
25 Incorrect 66 ms 389032 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 55 ms 377940 KB Output is correct
2 Correct 113 ms 371488 KB Output is correct
3 Correct 116 ms 371536 KB Output is correct
4 Correct 117 ms 371396 KB Output is correct
5 Correct 155 ms 371284 KB Output is correct
6 Correct 1434 ms 677720 KB Output is correct
7 Correct 1676 ms 721228 KB Output is correct
8 Runtime error 1999 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -