oj.uz

Submission #1055892

# Submission time Handle Problem Language Result Execution time Memory
1055892 2024-08-13T06:19:42 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 464 ms 164588 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];
vector<int> dp2[N];
int dp3[N][15],dp4[N][15];
vector<int> g[N],c[N],dA[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];
		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);
multiset<int> dp2C[N];
int Get(int u,int k){
	int &ret=dp[u][k];
	if(ret) return ret;
	if(dp2C[u].size()!=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) for(int i=0;i<(int)c[w].size();i++) if(i+1!=e) val=min(val,dfs1(c[w][i],b-d-1));
			}
			dp2[u][i]=val;
			dp2C[u].insert(dp2[u][i]);
		}
	}
	if(dA[u].empty()||(dA[u].size()==1&&k)){
		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) dp2C[u].erase(dp2C[u].lower_bound(dp2[u][k-1]));
		ret=*dp2C[u].rbegin();
		if(k) dp2C[u].insert(dp2[u][k-1]);
	}
	debug(u,k,ret);
	return ret;
}
int dfs1(int u,int d){
	if(d>=15) exit(0);
	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));
	debug(u,d,0,ret);
	return ret;
}
int dfs2(int u,int d){
	if(d>=15) exit(0);
	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));
	debug(u,d,1,ret);
	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 18 ms 49756 KB Output is correct
2 Correct 18 ms 49764 KB Output is correct
3 Correct 18 ms 49752 KB Output is correct
4 Correct 18 ms 49752 KB Output is correct
5 Correct 18 ms 49756 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 164588 KB Output is correct
2 Correct 339 ms 160468 KB Output is correct
3 Incorrect 153 ms 131524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49752 KB Output is correct
2 Incorrect 19 ms 49840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49752 KB Output is correct
2 Incorrect 19 ms 49840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 150344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49752 KB Output is correct
2 Incorrect 19 ms 49840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49756 KB Output is correct
2 Correct 18 ms 49764 KB Output is correct
3 Correct 18 ms 49752 KB Output is correct
4 Correct 18 ms 49752 KB Output is correct
5 Correct 18 ms 49756 KB Output is correct
6 Correct 464 ms 164588 KB Output is correct
7 Correct 339 ms 160468 KB Output is correct
8 Incorrect 153 ms 131524 KB Output isn't correct
9 Halted 0 ms 0 KB -