oj.uz

Submission #1056194

# Submission time Handle Problem Language Result Execution time Memory
1056194 2024-08-13T08:10:44 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 6000 ms 609616 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],dA[N],idxsubA[N];
void dfs0(int u){
	L[dep[u]]=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;
}
int dfs1(int u,int d);
int dfs2(int u,int d);
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 Get(int u,int k){
	int &ret=dp[u][k];
	if(ret) return ret;
	if((int)dp2C[u].size()!=(int)dA[u].size()){
		for(int i=0;i<(int)dA[u].size();i++){
			int v=dA[u][i];
			int val=dfs1(v,b),w=v,d=0,e=0;
			while(d<b){
				e=q[w];
				w=p[w];
				d++;
				val=min(val,Get(w,e));
				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((int)c[w].size()>1){
						dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
						val=min(val,-dp3D[w][b-d].top());
						dp3D[w][b-d].insert(-dfs1(c[w][e-1],b-d-1));
					}
				}
			}
			dp2[u][i]=val;
			dp2C[u].insert(dp2[u][i]);
		}
	}
	if(dA[u].empty()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
		if(k&&idxsubA[c[u][k-1]].empty()) ret=Get(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]);
		}
	}
	return ret;
}
int dfs1(int u,int d){
	int &ret=dp3[u][d];
	if(ret) return ret;
	ret=Get(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]);
	}
	ctop[r]=r;
	dfsH(r,1);
	for(int i=1;i<=n;i++){
		dp[i].resize(c[i].size()+1);
		dp2[i].resize(dA[i].size());
	}
	cout<<Get(r,0);
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 347228 KB Output is correct
2 Correct 44 ms 347172 KB Output is correct
3 Correct 44 ms 347228 KB Output is correct
4 Correct 46 ms 347216 KB Output is correct
5 Correct 43 ms 347256 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 544852 KB Output is correct
2 Correct 632 ms 502848 KB Output is correct
3 Correct 1002 ms 609616 KB Output is correct
4 Execution timed out 6074 ms 468312 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 355668 KB Output is correct
2 Correct 47 ms 355668 KB Output is correct
3 Correct 45 ms 355668 KB Output is correct
4 Correct 45 ms 355664 KB Output is correct
5 Correct 45 ms 355664 KB Output is correct
6 Correct 45 ms 355668 KB Output is correct
7 Correct 45 ms 355664 KB Output is correct
8 Correct 48 ms 353548 KB Output is correct
9 Correct 43 ms 347216 KB Output is correct
10 Correct 44 ms 355556 KB Output is correct
11 Correct 46 ms 355676 KB Output is correct
12 Correct 45 ms 355412 KB Output is correct
13 Correct 45 ms 355412 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 355668 KB Output is correct
2 Correct 47 ms 355668 KB Output is correct
3 Correct 45 ms 355668 KB Output is correct
4 Correct 45 ms 355664 KB Output is correct
5 Correct 45 ms 355664 KB Output is correct
6 Correct 45 ms 355668 KB Output is correct
7 Correct 45 ms 355664 KB Output is correct
8 Correct 48 ms 353548 KB Output is correct
9 Correct 43 ms 347216 KB Output is correct
10 Correct 44 ms 355556 KB Output is correct
11 Correct 46 ms 355676 KB Output is correct
12 Correct 45 ms 355412 KB Output is correct
13 Correct 45 ms 355412 KB Output is correct
14 Correct 47 ms 356176 KB Output is correct
15 Correct 49 ms 356176 KB Output is correct
16 Correct 49 ms 356180 KB Output is correct
17 Correct 47 ms 356180 KB Output is correct
18 Correct 46 ms 356176 KB Output is correct
19 Correct 50 ms 356176 KB Output is correct
20 Correct 47 ms 356180 KB Output is correct
21 Correct 49 ms 353616 KB Output is correct
22 Correct 45 ms 347224 KB Output is correct
23 Correct 51 ms 356960 KB Output is correct
24 Correct 48 ms 356432 KB Output is correct
25 Incorrect 53 ms 357196 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 138 ms 381264 KB Output is correct
2 Correct 150 ms 383716 KB Output is correct
3 Correct 143 ms 381776 KB Output is correct
4 Correct 148 ms 382952 KB Output is correct
5 Correct 127 ms 379920 KB Output is correct
6 Correct 152 ms 380816 KB Output is correct
7 Correct 168 ms 385504 KB Output is correct
8 Correct 80 ms 367188 KB Output is correct
9 Correct 262 ms 391784 KB Output is correct
10 Correct 108 ms 376916 KB Output is correct
11 Correct 81 ms 363764 KB Output is correct
12 Correct 87 ms 367220 KB Output is correct
13 Correct 46 ms 347404 KB Output is correct
14 Correct 47 ms 347276 KB Output is correct
15 Correct 227 ms 387100 KB Output is correct
16 Correct 108 ms 378040 KB Output is correct
17 Correct 123 ms 377976 KB Output is correct
18 Correct 113 ms 377684 KB Output is correct
19 Correct 128 ms 386324 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 355668 KB Output is correct
2 Correct 47 ms 355668 KB Output is correct
3 Correct 45 ms 355668 KB Output is correct
4 Correct 45 ms 355664 KB Output is correct
5 Correct 45 ms 355664 KB Output is correct
6 Correct 45 ms 355668 KB Output is correct
7 Correct 45 ms 355664 KB Output is correct
8 Correct 48 ms 353548 KB Output is correct
9 Correct 43 ms 347216 KB Output is correct
10 Correct 44 ms 355556 KB Output is correct
11 Correct 46 ms 355676 KB Output is correct
12 Correct 45 ms 355412 KB Output is correct
13 Correct 45 ms 355412 KB Output is correct
14 Correct 47 ms 356176 KB Output is correct
15 Correct 49 ms 356176 KB Output is correct
16 Correct 49 ms 356180 KB Output is correct
17 Correct 47 ms 356180 KB Output is correct
18 Correct 46 ms 356176 KB Output is correct
19 Correct 50 ms 356176 KB Output is correct
20 Correct 47 ms 356180 KB Output is correct
21 Correct 49 ms 353616 KB Output is correct
22 Correct 45 ms 347224 KB Output is correct
23 Correct 51 ms 356960 KB Output is correct
24 Correct 48 ms 356432 KB Output is correct
25 Incorrect 53 ms 357196 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 46 ms 347228 KB Output is correct
2 Correct 44 ms 347172 KB Output is correct
3 Correct 44 ms 347228 KB Output is correct
4 Correct 46 ms 347216 KB Output is correct
5 Correct 43 ms 347256 KB Output is correct
6 Correct 899 ms 544852 KB Output is correct
7 Correct 632 ms 502848 KB Output is correct
8 Correct 1002 ms 609616 KB Output is correct
9 Execution timed out 6074 ms 468312 KB Time limit exceeded
10 Halted 0 ms 0 KB -