oj.uz

Submission #1056002

# Submission time Handle Problem Language Result Execution time Memory
1056002 2024-08-13T07:03:45 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 677 ms 221096 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];
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);
	}
	int idx=0;
	for(int v: g[u]) if(p[u]!=v){
		dep[v]=dep[u]+1;
		p[v]=u;
		q[v]=++idx;
		c[u].push_back(v);
		dfs0(v);
	}
}
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],dpC[N];
int 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(!dp3D[w][b-d]){
						dp3D[w][b-d]=1e9;
						for(int j=0;j<(int)c[w].size();j++) dp3D[w][b-d]=min(dp3D[w][b-d],dfs1(c[w][j],b-d-1));
					}
					val=min(val,dp3D[w][b-d]);
				}
			}
			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 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 35 ms 80216 KB Output is correct
2 Correct 28 ms 80220 KB Output is correct
3 Correct 38 ms 80212 KB Output is correct
4 Correct 38 ms 80164 KB Output is correct
5 Correct 35 ms 80212 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 221096 KB Output is correct
2 Incorrect 492 ms 220140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 80208 KB Output is correct
2 Correct 42 ms 80380 KB Output is correct
3 Correct 28 ms 80220 KB Output is correct
4 Correct 29 ms 80216 KB Output is correct
5 Correct 42 ms 80448 KB Output is correct
6 Correct 28 ms 80220 KB Output is correct
7 Correct 31 ms 80388 KB Output is correct
8 Correct 27 ms 80220 KB Output is correct
9 Correct 40 ms 80216 KB Output is correct
10 Correct 26 ms 80208 KB Output is correct
11 Incorrect 32 ms 80468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 80208 KB Output is correct
2 Correct 42 ms 80380 KB Output is correct
3 Correct 28 ms 80220 KB Output is correct
4 Correct 29 ms 80216 KB Output is correct
5 Correct 42 ms 80448 KB Output is correct
6 Correct 28 ms 80220 KB Output is correct
7 Correct 31 ms 80388 KB Output is correct
8 Correct 27 ms 80220 KB Output is correct
9 Correct 40 ms 80216 KB Output is correct
10 Correct 26 ms 80208 KB Output is correct
11 Incorrect 32 ms 80468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 113232 KB Output is correct
2 Correct 124 ms 114240 KB Output is correct
3 Correct 119 ms 112664 KB Output is correct
4 Correct 135 ms 113488 KB Output is correct
5 Correct 106 ms 107348 KB Output is correct
6 Correct 109 ms 108368 KB Output is correct
7 Correct 165 ms 112140 KB Output is correct
8 Correct 63 ms 96216 KB Output is correct
9 Incorrect 151 ms 111216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 80208 KB Output is correct
2 Correct 42 ms 80380 KB Output is correct
3 Correct 28 ms 80220 KB Output is correct
4 Correct 29 ms 80216 KB Output is correct
5 Correct 42 ms 80448 KB Output is correct
6 Correct 28 ms 80220 KB Output is correct
7 Correct 31 ms 80388 KB Output is correct
8 Correct 27 ms 80220 KB Output is correct
9 Correct 40 ms 80216 KB Output is correct
10 Correct 26 ms 80208 KB Output is correct
11 Incorrect 32 ms 80468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 80216 KB Output is correct
2 Correct 28 ms 80220 KB Output is correct
3 Correct 38 ms 80212 KB Output is correct
4 Correct 38 ms 80164 KB Output is correct
5 Correct 35 ms 80212 KB Output is correct
6 Correct 677 ms 221096 KB Output is correct
7 Incorrect 492 ms 220140 KB Output isn't correct
8 Halted 0 ms 0 KB -