oj.uz

Submission #1055819

# Submission time Handle Problem Language Result Execution time Memory
1055819 2024-08-13T05:50:16 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 5 ms 5724 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=3005;
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][N],dp4[N][N];
vector<int> g[N],c[N],dA[N];
void dfs0(int u){
	if(dep[u]>=a){
		pA[u]=L[dep[u]-a];
		subA[u]=L[dep[u]-a+1];
		dA[pA[u]].push_back(u);
	}
	L[dep[u]]=u;
	int idx=0;
	for(int v: g[u]) if(p[u]!=v){
		dep[v]=dep[u]+1;
		p[v]=u;
		q[u]=++idx;
		c[u].push_back(v);
		dfs0(v);
	}
}
int dfs1(int u,int d);
int dfs2(int u,int d);
int Get(int u,int k){
	int &ret=dp[u][k];
	if(ret) return ret;
	for(int i=0;i<(int)dA[u].size();i++){
		int v=dA[u][i];
		if(q[subA[v]]==k) continue;
		if(dp2[u][i]){
			ret=max(ret,dp2[u][i]);
			continue;
		}
		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));
		}
		ret=max(ret,val);
	}
	if(!ret){
		ret=u;
		for(int i=0;i<(int)c[u].size();i++) if(i+1!=k) ret=min(ret,dfs2(u,b-1));
	}
	debug(u,k,ret);
	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));
	debug(u,d,ret);
	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));
	debug(u,d,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;
	}
	if(n>3000) 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 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

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

Subtask #4
0.0 / 3.0

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

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

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

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -