oj.uz

Submission #1056348

# Submission time Handle Problem Language Result Execution time Memory
1056348 2024-08-13T08:58:09 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
5 / 25
 664 ms 532564 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>;
using ti4=array<int,4>;
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];
vector<ti4> qry[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]);
						int d=dep[v]-dep[w];
						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(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));
						}
						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 54 ms 384092 KB Output is correct
2 Correct 50 ms 384080 KB Output is correct
3 Correct 53 ms 384324 KB Output is correct
4 Correct 57 ms 384320 KB Output is correct
5 Correct 49 ms 384316 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 526432 KB Output is correct
2 Correct 617 ms 532564 KB Output is correct
3 Correct 309 ms 524884 KB Output is correct
4 Correct 312 ms 520160 KB Output is correct
5 Incorrect 586 ms 530260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 390480 KB Output is correct
2 Correct 49 ms 390488 KB Output is correct
3 Correct 51 ms 390372 KB Output is correct
4 Incorrect 54 ms 390492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 390480 KB Output is correct
2 Correct 49 ms 390488 KB Output is correct
3 Correct 51 ms 390372 KB Output is correct
4 Incorrect 54 ms 390492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 423240 KB Output is correct
2 Correct 241 ms 424016 KB Output is correct
3 Correct 211 ms 422740 KB Output is correct
4 Correct 207 ms 423032 KB Output is correct
5 Correct 181 ms 420180 KB Output is correct
6 Correct 217 ms 421144 KB Output is correct
7 Correct 251 ms 424324 KB Output is correct
8 Correct 127 ms 409000 KB Output is correct
9 Correct 256 ms 426744 KB Output is correct
10 Correct 214 ms 421576 KB Output is correct
11 Correct 130 ms 407888 KB Output is correct
12 Correct 124 ms 409400 KB Output is correct
13 Correct 49 ms 384088 KB Output is correct
14 Correct 48 ms 384092 KB Output is correct
15 Correct 196 ms 421712 KB Output is correct
16 Correct 137 ms 418948 KB Output is correct
17 Correct 133 ms 419160 KB Output is correct
18 Correct 125 ms 418884 KB Output is correct
19 Correct 195 ms 438944 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 390480 KB Output is correct
2 Correct 49 ms 390488 KB Output is correct
3 Correct 51 ms 390372 KB Output is correct
4 Incorrect 54 ms 390492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 384092 KB Output is correct
2 Correct 50 ms 384080 KB Output is correct
3 Correct 53 ms 384324 KB Output is correct
4 Correct 57 ms 384320 KB Output is correct
5 Correct 49 ms 384316 KB Output is correct
6 Correct 664 ms 526432 KB Output is correct
7 Correct 617 ms 532564 KB Output is correct
8 Correct 309 ms 524884 KB Output is correct
9 Correct 312 ms 520160 KB Output is correct
10 Incorrect 586 ms 530260 KB Output isn't correct
11 Halted 0 ms 0 KB -