oj.uz

Submission #1056669

# Submission time Handle Problem Language Result Execution time Memory
1056669 2024-08-13T10:31:53 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
25 / 25
 893 ms 291488 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]);
					}
				}
			}
			if(c[u].size()){
				for(auto [e,d,v,i]: qry[u]) if(e!=1){
					auto iter=S[1][c[u][0]].lower_bound({dep[u]+d,(int)1e9});
					if(iter==S[1][c[u][0]].begin()) continue;
					iter--;
					dp2[v][i]=min(dp2[v][i],(*iter)[1]);
				}
			}
			sort(qry[u].begin(),qry[u].end());
			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 16 ms 127836 KB Output is correct
2 Correct 21 ms 127836 KB Output is correct
3 Correct 19 ms 127836 KB Output is correct
4 Correct 18 ms 127840 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 765 ms 266780 KB Output is correct
2 Correct 700 ms 266496 KB Output is correct
3 Correct 433 ms 280520 KB Output is correct
4 Correct 423 ms 271952 KB Output is correct
5 Correct 716 ms 255832 KB Output is correct
6 Correct 401 ms 219544 KB Output is correct
7 Correct 389 ms 219580 KB Output is correct
8 Correct 581 ms 243288 KB Output is correct
9 Correct 17 ms 128088 KB Output is correct
10 Correct 769 ms 266908 KB Output is correct
11 Correct 718 ms 266652 KB Output is correct
12 Correct 17 ms 127576 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 134108 KB Output is correct
2 Correct 18 ms 133980 KB Output is correct
3 Correct 19 ms 133976 KB Output is correct
4 Correct 17 ms 133976 KB Output is correct
5 Correct 17 ms 133980 KB Output is correct
6 Correct 19 ms 133980 KB Output is correct
7 Correct 18 ms 133980 KB Output is correct
8 Correct 19 ms 133996 KB Output is correct
9 Correct 17 ms 127580 KB Output is correct
10 Correct 17 ms 133976 KB Output is correct
11 Correct 22 ms 133908 KB Output is correct
12 Correct 22 ms 133968 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 134108 KB Output is correct
2 Correct 18 ms 133980 KB Output is correct
3 Correct 19 ms 133976 KB Output is correct
4 Correct 17 ms 133976 KB Output is correct
5 Correct 17 ms 133980 KB Output is correct
6 Correct 19 ms 133980 KB Output is correct
7 Correct 18 ms 133980 KB Output is correct
8 Correct 19 ms 133996 KB Output is correct
9 Correct 17 ms 127580 KB Output is correct
10 Correct 17 ms 133976 KB Output is correct
11 Correct 22 ms 133908 KB Output is correct
12 Correct 22 ms 133968 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct
14 Correct 21 ms 134748 KB Output is correct
15 Correct 21 ms 134748 KB Output is correct
16 Correct 21 ms 134748 KB Output is correct
17 Correct 21 ms 134748 KB Output is correct
18 Correct 21 ms 134748 KB Output is correct
19 Correct 21 ms 134748 KB Output is correct
20 Correct 23 ms 134908 KB Output is correct
21 Correct 19 ms 134748 KB Output is correct
22 Correct 18 ms 127836 KB Output is correct
23 Correct 28 ms 134824 KB Output is correct
24 Correct 27 ms 134972 KB Output is correct
25 Correct 21 ms 135004 KB Output is correct
26 Correct 23 ms 134716 KB Output is correct
27 Correct 18 ms 134492 KB Output is correct
28 Correct 19 ms 134504 KB Output is correct
29 Correct 21 ms 134736 KB Output is correct
30 Correct 24 ms 134748 KB Output is correct
31 Correct 25 ms 134884 KB Output is correct
32 Correct 21 ms 134744 KB Output is correct
33 Correct 22 ms 135256 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 164800 KB Output is correct
2 Correct 239 ms 165968 KB Output is correct
3 Correct 182 ms 164176 KB Output is correct
4 Correct 193 ms 163712 KB Output is correct
5 Correct 183 ms 164180 KB Output is correct
6 Correct 229 ms 164424 KB Output is correct
7 Correct 189 ms 165460 KB Output is correct
8 Correct 118 ms 158252 KB Output is correct
9 Correct 191 ms 166224 KB Output is correct
10 Correct 155 ms 162736 KB Output is correct
11 Correct 110 ms 155988 KB Output is correct
12 Correct 112 ms 160348 KB Output is correct
13 Correct 17 ms 127576 KB Output is correct
14 Correct 18 ms 127832 KB Output is correct
15 Correct 160 ms 162020 KB Output is correct
16 Correct 155 ms 162748 KB Output is correct
17 Correct 140 ms 164264 KB Output is correct
18 Correct 149 ms 162824 KB Output is correct
19 Correct 204 ms 176468 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 134108 KB Output is correct
2 Correct 18 ms 133980 KB Output is correct
3 Correct 19 ms 133976 KB Output is correct
4 Correct 17 ms 133976 KB Output is correct
5 Correct 17 ms 133980 KB Output is correct
6 Correct 19 ms 133980 KB Output is correct
7 Correct 18 ms 133980 KB Output is correct
8 Correct 19 ms 133996 KB Output is correct
9 Correct 17 ms 127580 KB Output is correct
10 Correct 17 ms 133976 KB Output is correct
11 Correct 22 ms 133908 KB Output is correct
12 Correct 22 ms 133968 KB Output is correct
13 Correct 17 ms 133980 KB Output is correct
14 Correct 21 ms 134748 KB Output is correct
15 Correct 21 ms 134748 KB Output is correct
16 Correct 21 ms 134748 KB Output is correct
17 Correct 21 ms 134748 KB Output is correct
18 Correct 21 ms 134748 KB Output is correct
19 Correct 21 ms 134748 KB Output is correct
20 Correct 23 ms 134908 KB Output is correct
21 Correct 19 ms 134748 KB Output is correct
22 Correct 18 ms 127836 KB Output is correct
23 Correct 28 ms 134824 KB Output is correct
24 Correct 27 ms 134972 KB Output is correct
25 Correct 21 ms 135004 KB Output is correct
26 Correct 23 ms 134716 KB Output is correct
27 Correct 18 ms 134492 KB Output is correct
28 Correct 19 ms 134504 KB Output is correct
29 Correct 21 ms 134736 KB Output is correct
30 Correct 24 ms 134748 KB Output is correct
31 Correct 25 ms 134884 KB Output is correct
32 Correct 21 ms 134744 KB Output is correct
33 Correct 22 ms 135256 KB Output is correct
34 Correct 188 ms 166068 KB Output is correct
35 Correct 227 ms 164380 KB Output is correct
36 Correct 197 ms 165716 KB Output is correct
37 Correct 230 ms 163664 KB Output is correct
38 Correct 182 ms 162928 KB Output is correct
39 Correct 185 ms 164356 KB Output is correct
40 Correct 210 ms 165596 KB Output is correct
41 Correct 117 ms 158156 KB Output is correct
42 Correct 18 ms 127708 KB Output is correct
43 Correct 188 ms 165000 KB Output is correct
44 Correct 123 ms 162828 KB Output is correct
45 Correct 147 ms 163120 KB Output is correct
46 Correct 137 ms 164412 KB Output is correct
47 Correct 102 ms 162484 KB Output is correct
48 Correct 145 ms 170132 KB Output is correct
49 Correct 236 ms 164692 KB Output is correct
50 Correct 143 ms 160144 KB Output is correct
51 Correct 136 ms 157904 KB Output is correct
52 Correct 106 ms 157424 KB Output is correct
53 Correct 108 ms 158936 KB Output is correct
54 Correct 90 ms 157640 KB Output is correct
55 Correct 161 ms 169736 KB Output is correct
56 Correct 169 ms 170064 KB Output is correct
57 Correct 229 ms 183236 KB Output is correct
58 Correct 316 ms 182220 KB Output is correct

Subtask #7
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 127836 KB Output is correct
2 Correct 21 ms 127836 KB Output is correct
3 Correct 19 ms 127836 KB Output is correct
4 Correct 18 ms 127840 KB Output is correct
5 Correct 17 ms 127580 KB Output is correct
6 Correct 765 ms 266780 KB Output is correct
7 Correct 700 ms 266496 KB Output is correct
8 Correct 433 ms 280520 KB Output is correct
9 Correct 423 ms 271952 KB Output is correct
10 Correct 716 ms 255832 KB Output is correct
11 Correct 401 ms 219544 KB Output is correct
12 Correct 389 ms 219580 KB Output is correct
13 Correct 581 ms 243288 KB Output is correct
14 Correct 17 ms 128088 KB Output is correct
15 Correct 769 ms 266908 KB Output is correct
16 Correct 718 ms 266652 KB Output is correct
17 Correct 17 ms 127576 KB Output is correct
18 Correct 22 ms 134108 KB Output is correct
19 Correct 18 ms 133980 KB Output is correct
20 Correct 19 ms 133976 KB Output is correct
21 Correct 17 ms 133976 KB Output is correct
22 Correct 17 ms 133980 KB Output is correct
23 Correct 19 ms 133980 KB Output is correct
24 Correct 18 ms 133980 KB Output is correct
25 Correct 19 ms 133996 KB Output is correct
26 Correct 17 ms 127580 KB Output is correct
27 Correct 17 ms 133976 KB Output is correct
28 Correct 22 ms 133908 KB Output is correct
29 Correct 22 ms 133968 KB Output is correct
30 Correct 17 ms 133980 KB Output is correct
31 Correct 21 ms 134748 KB Output is correct
32 Correct 21 ms 134748 KB Output is correct
33 Correct 21 ms 134748 KB Output is correct
34 Correct 21 ms 134748 KB Output is correct
35 Correct 21 ms 134748 KB Output is correct
36 Correct 21 ms 134748 KB Output is correct
37 Correct 23 ms 134908 KB Output is correct
38 Correct 19 ms 134748 KB Output is correct
39 Correct 18 ms 127836 KB Output is correct
40 Correct 28 ms 134824 KB Output is correct
41 Correct 27 ms 134972 KB Output is correct
42 Correct 21 ms 135004 KB Output is correct
43 Correct 23 ms 134716 KB Output is correct
44 Correct 18 ms 134492 KB Output is correct
45 Correct 19 ms 134504 KB Output is correct
46 Correct 21 ms 134736 KB Output is correct
47 Correct 24 ms 134748 KB Output is correct
48 Correct 25 ms 134884 KB Output is correct
49 Correct 21 ms 134744 KB Output is correct
50 Correct 22 ms 135256 KB Output is correct
51 Correct 189 ms 164800 KB Output is correct
52 Correct 239 ms 165968 KB Output is correct
53 Correct 182 ms 164176 KB Output is correct
54 Correct 193 ms 163712 KB Output is correct
55 Correct 183 ms 164180 KB Output is correct
56 Correct 229 ms 164424 KB Output is correct
57 Correct 189 ms 165460 KB Output is correct
58 Correct 118 ms 158252 KB Output is correct
59 Correct 191 ms 166224 KB Output is correct
60 Correct 155 ms 162736 KB Output is correct
61 Correct 110 ms 155988 KB Output is correct
62 Correct 112 ms 160348 KB Output is correct
63 Correct 17 ms 127576 KB Output is correct
64 Correct 18 ms 127832 KB Output is correct
65 Correct 160 ms 162020 KB Output is correct
66 Correct 155 ms 162748 KB Output is correct
67 Correct 140 ms 164264 KB Output is correct
68 Correct 149 ms 162824 KB Output is correct
69 Correct 204 ms 176468 KB Output is correct
70 Correct 188 ms 166068 KB Output is correct
71 Correct 227 ms 164380 KB Output is correct
72 Correct 197 ms 165716 KB Output is correct
73 Correct 230 ms 163664 KB Output is correct
74 Correct 182 ms 162928 KB Output is correct
75 Correct 185 ms 164356 KB Output is correct
76 Correct 210 ms 165596 KB Output is correct
77 Correct 117 ms 158156 KB Output is correct
78 Correct 18 ms 127708 KB Output is correct
79 Correct 188 ms 165000 KB Output is correct
80 Correct 123 ms 162828 KB Output is correct
81 Correct 147 ms 163120 KB Output is correct
82 Correct 137 ms 164412 KB Output is correct
83 Correct 102 ms 162484 KB Output is correct
84 Correct 145 ms 170132 KB Output is correct
85 Correct 236 ms 164692 KB Output is correct
86 Correct 143 ms 160144 KB Output is correct
87 Correct 136 ms 157904 KB Output is correct
88 Correct 106 ms 157424 KB Output is correct
89 Correct 108 ms 158936 KB Output is correct
90 Correct 90 ms 157640 KB Output is correct
91 Correct 161 ms 169736 KB Output is correct
92 Correct 169 ms 170064 KB Output is correct
93 Correct 229 ms 183236 KB Output is correct
94 Correct 316 ms 182220 KB Output is correct
95 Correct 715 ms 227196 KB Output is correct
96 Correct 743 ms 229556 KB Output is correct
97 Correct 639 ms 227656 KB Output is correct
98 Correct 716 ms 223568 KB Output is correct
99 Correct 607 ms 221176 KB Output is correct
100 Correct 699 ms 225364 KB Output is correct
101 Correct 765 ms 228692 KB Output is correct
102 Correct 435 ms 211004 KB Output is correct
103 Correct 16 ms 127832 KB Output is correct
104 Correct 576 ms 217428 KB Output is correct
105 Correct 445 ms 221756 KB Output is correct
106 Correct 457 ms 223708 KB Output is correct
107 Correct 457 ms 223548 KB Output is correct
108 Correct 285 ms 223336 KB Output is correct
109 Correct 639 ms 247076 KB Output is correct
110 Correct 671 ms 230348 KB Output is correct
111 Correct 514 ms 219072 KB Output is correct
112 Correct 380 ms 210600 KB Output is correct
113 Correct 402 ms 209548 KB Output is correct
114 Correct 340 ms 209728 KB Output is correct
115 Correct 319 ms 209088 KB Output is correct
116 Correct 597 ms 245844 KB Output is correct
117 Correct 567 ms 247364 KB Output is correct
118 Correct 846 ms 291488 KB Output is correct
119 Correct 893 ms 263324 KB Output is correct