oj.uz

Submission #1056559

# Submission time Handle Problem Language Result Execution time Memory
1056559 2024-08-13T10:03:13 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 685 ms 283472 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);
	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()){
				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]){
					e--;
					while(prv-1>e){
						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]);
				}
				while(prv>0){
					prv--;
					mrg(1,u,c[u][prv]);
				}
			}
			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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 127836 KB Output is correct
2 Correct 19 ms 127704 KB Output is correct
3 Correct 17 ms 127836 KB Output is correct
4 Correct 17 ms 127848 KB Output is correct
5 Correct 17 ms 127580 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 269904 KB Output is correct
2 Correct 685 ms 269396 KB Output is correct
3 Correct 370 ms 283472 KB Output is correct
4 Correct 376 ms 275304 KB Output is correct
5 Correct 658 ms 259668 KB Output is correct
6 Correct 333 ms 223060 KB Output is correct
7 Correct 325 ms 223240 KB Output is correct
8 Correct 534 ms 247124 KB Output is correct
9 Correct 16 ms 127836 KB Output is correct
10 Correct 668 ms 270420 KB Output is correct
11 Correct 664 ms 270420 KB Output is correct
12 Correct 17 ms 127832 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 133980 KB Output is correct
2 Correct 17 ms 134000 KB Output is correct
3 Correct 17 ms 133980 KB Output is correct
4 Correct 18 ms 133976 KB Output is correct
5 Correct 18 ms 133980 KB Output is correct
6 Correct 17 ms 133980 KB Output is correct
7 Correct 17 ms 134108 KB Output is correct
8 Correct 18 ms 133980 KB Output is correct
9 Correct 18 ms 127836 KB Output is correct
10 Correct 18 ms 133976 KB Output is correct
11 Correct 18 ms 133980 KB Output is correct
12 Correct 17 ms 133976 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 133980 KB Output is correct
2 Correct 17 ms 134000 KB Output is correct
3 Correct 17 ms 133980 KB Output is correct
4 Correct 18 ms 133976 KB Output is correct
5 Correct 18 ms 133980 KB Output is correct
6 Correct 17 ms 133980 KB Output is correct
7 Correct 17 ms 134108 KB Output is correct
8 Correct 18 ms 133980 KB Output is correct
9 Correct 18 ms 127836 KB Output is correct
10 Correct 18 ms 133976 KB Output is correct
11 Correct 18 ms 133980 KB Output is correct
12 Correct 17 ms 133976 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct
14 Incorrect 21 ms 134760 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 165972 KB Output is correct
2 Incorrect 183 ms 166924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 133980 KB Output is correct
2 Correct 17 ms 134000 KB Output is correct
3 Correct 17 ms 133980 KB Output is correct
4 Correct 18 ms 133976 KB Output is correct
5 Correct 18 ms 133980 KB Output is correct
6 Correct 17 ms 133980 KB Output is correct
7 Correct 17 ms 134108 KB Output is correct
8 Correct 18 ms 133980 KB Output is correct
9 Correct 18 ms 127836 KB Output is correct
10 Correct 18 ms 133976 KB Output is correct
11 Correct 18 ms 133980 KB Output is correct
12 Correct 17 ms 133976 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct
14 Incorrect 21 ms 134760 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 127836 KB Output is correct
2 Correct 19 ms 127704 KB Output is correct
3 Correct 17 ms 127836 KB Output is correct
4 Correct 17 ms 127848 KB Output is correct
5 Correct 17 ms 127580 KB Output is correct
6 Correct 676 ms 269904 KB Output is correct
7 Correct 685 ms 269396 KB Output is correct
8 Correct 370 ms 283472 KB Output is correct
9 Correct 376 ms 275304 KB Output is correct
10 Correct 658 ms 259668 KB Output is correct
11 Correct 333 ms 223060 KB Output is correct
12 Correct 325 ms 223240 KB Output is correct
13 Correct 534 ms 247124 KB Output is correct
14 Correct 16 ms 127836 KB Output is correct
15 Correct 668 ms 270420 KB Output is correct
16 Correct 664 ms 270420 KB Output is correct
17 Correct 17 ms 127832 KB Output is correct
18 Correct 18 ms 133980 KB Output is correct
19 Correct 17 ms 134000 KB Output is correct
20 Correct 17 ms 133980 KB Output is correct
21 Correct 18 ms 133976 KB Output is correct
22 Correct 18 ms 133980 KB Output is correct
23 Correct 17 ms 133980 KB Output is correct
24 Correct 17 ms 134108 KB Output is correct
25 Correct 18 ms 133980 KB Output is correct
26 Correct 18 ms 127836 KB Output is correct
27 Correct 18 ms 133976 KB Output is correct
28 Correct 18 ms 133980 KB Output is correct
29 Correct 17 ms 133976 KB Output is correct
30 Correct 17 ms 133980 KB Output is correct
31 Incorrect 21 ms 134760 KB Output isn't correct
32 Halted 0 ms 0 KB -