oj.uz

답안 #1056504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056504 2024-08-13T09:49:31 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 823 ms 280844 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];
set<pii> S[2][N];
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]=(int)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 (int)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];
void ins(int c,int u,pii p){
	auto iter=S[c][u].lower_bound({p[0],-1});
	while(iter!=S[c][u].end()&&p[1]>=(*iter)[1]) iter=S[c][u].erase(iter);
	if(iter!=S[c][u].begin()){
		iter--;
		if((*iter)[1]<=p[1]) return;
	}
	S[c][u].insert(p);
}
void mrg(int c,int u,int v){
	if(S[c][u].size()<S[c][v].size()) swap(S[c][u],S[c][v]);
	for(pii p: S[c][v]) ins(c,u,p);
}
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(int u: dL[D]){
			for(int i=0;i<(int)dA[u].size();i++){
				int v=dA[u][i],w=v,e=0;
				dp2[u][i]=(int)1e9;
				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)];
					int d=dep[v]-dep[w];
					if(d<b) qry[w].push_back({e,b-d,u,i});
					e=q[ww];
					w=p[ww];
				}
			}
		}
	}
	for(int D=n;D>=0;D--){
		for(auto [u,v]: ev[D]) T.upd(1,1,n,in[v],dp[u][0]);
		for(int u: dL[D]){
			for(int i=0;i<(int)dA[u].size();i++){
				int v=dA[u][i];
				int &ret=dp2[u][i],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)];
					if(in[ww]<=in[w]-1) ret=min(ret,T.qry(1,1,n,in[ww],in[w]-1));
					ret=min(ret,dp[w][e]);
					e=q[ww];
					w=p[ww];
				}
				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){
							auto iter=S[0][c[u][i]].lower_bound({dep[u]+b,(int)1e9});
							iter--;
							ret=min(ret,(*iter)[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]);
					}
				}
			}
			sort(qry[u].begin(),qry[u].end());
			if(c[u].size()){
				for(auto [e,d,v,i]: qry[u]){
					if(e!=1){
						auto iter=S[0][c[u][0]].lower_bound({dep[u]+d,(int)1e9});
						if(iter==S[0][c[u][0]].begin()) continue;
						iter--;
						dp2[v][i]=min(dp2[v][i],(*iter)[1]);
					}
				}
				int prv=0;
				for(auto [e,d,v,i]: qry[u]) if(e>1){
					e--;
					while(prv+1<e){
						prv++;
						set<pii> SS=S[1][c[u][prv]];
						mrg(1,u,c[u][prv]);
						S[1][c[u][prv]]=SS;
					}
					auto iter=S[1][u].lower_bound({dep[u]+d,(int)1e9});
					if(iter==S[1][u].begin()) continue;
					iter--;
					dp2[v][i]=min(dp2[v][i],(*iter)[1]);
				}
				S[1][u].clear();
				reverse(qry[u].begin(),qry[u].end());
				prv=c[u].size();
				for(auto [e,d,v,i]: qry[u]) if(e){
					e--;
					while(prv-1>e){
						prv--;
						set<pii> SS=S[1][c[u][prv]];
						mrg(1,u,c[u][prv]);
					}
					auto iter=S[1][u].lower_bound({dep[u]+d,(int)1e9});
					if(iter==S[1][u].begin()) continue;
					iter--;
					dp2[v][i]=min(dp2[v][i],(*iter)[1]);
				}
			}
			ins(0,u,{dep[u],u});
			ins(1,u,{dep[u],dp[u][0]});
			for(int v: c[u]) mrg(0,u,v);
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 127580 KB Output is correct
2 Correct 17 ms 127836 KB Output is correct
3 Correct 19 ms 127844 KB Output is correct
4 Correct 18 ms 127836 KB Output is correct
5 Correct 17 ms 127836 KB Output is correct

Subtask #2
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 823 ms 280844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 134108 KB Output is correct
2 Incorrect 23 ms 133976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 134108 KB Output is correct
2 Incorrect 23 ms 133976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 209 ms 166828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 134108 KB Output is correct
2 Incorrect 23 ms 133976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 127580 KB Output is correct
2 Correct 17 ms 127836 KB Output is correct
3 Correct 19 ms 127844 KB Output is correct
4 Correct 18 ms 127836 KB Output is correct
5 Correct 17 ms 127836 KB Output is correct
6 Incorrect 823 ms 280844 KB Output isn't correct
7 Halted 0 ms 0 KB -