oj.uz

Submission #1055906

# Submission time Handle Problem Language Result Execution time Memory
1055906 2024-08-13T06:29:25 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 6000 ms 302936 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);
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()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
		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(dp2C[u].lower_bound(dp2[u][i]));
			}
		}
		ret=*dp2C[u].rbegin();
		if(k){
			for(int i: idxsubA[c[u][k-1]]) dp2C[u].insert(dp2[u][i]);
		}
	}
	debug(u,k,ret);
	return ret;
}
int dfs1(int u,int d){
	assert(d<=10);
	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){
	assert(d<=10);
	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 21 ms 56668 KB Output is correct
2 Correct 21 ms 56664 KB Output is correct
3 Correct 22 ms 56668 KB Output is correct
4 Correct 23 ms 56872 KB Output is correct
5 Correct 21 ms 56664 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 184148 KB Output is correct
2 Runtime error 365 ms 302936 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56736 KB Output is correct
2 Correct 24 ms 56928 KB Output is correct
3 Correct 21 ms 56924 KB Output is correct
4 Correct 21 ms 56920 KB Output is correct
5 Correct 24 ms 57252 KB Output is correct
6 Correct 21 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 22 ms 56668 KB Output is correct
9 Correct 21 ms 56792 KB Output is correct
10 Runtime error 55 ms 115016 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56736 KB Output is correct
2 Correct 24 ms 56928 KB Output is correct
3 Correct 21 ms 56924 KB Output is correct
4 Correct 21 ms 56920 KB Output is correct
5 Correct 24 ms 57252 KB Output is correct
6 Correct 21 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 22 ms 56668 KB Output is correct
9 Correct 21 ms 56792 KB Output is correct
10 Runtime error 55 ms 115016 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 87044 KB Output is correct
2 Correct 107 ms 87892 KB Output is correct
3 Correct 108 ms 86436 KB Output is correct
4 Correct 109 ms 87380 KB Output is correct
5 Correct 106 ms 86940 KB Output is correct
6 Correct 105 ms 87892 KB Output is correct
7 Correct 120 ms 86716 KB Output is correct
8 Correct 67 ms 72784 KB Output is correct
9 Correct 138 ms 85708 KB Output is correct
10 Correct 75 ms 79952 KB Output is correct
11 Correct 53 ms 66224 KB Output is correct
12 Correct 53 ms 71696 KB Output is correct
13 Correct 21 ms 56668 KB Output is correct
14 Correct 22 ms 56792 KB Output is correct
15 Correct 148 ms 81284 KB Output is correct
16 Execution timed out 6025 ms 79776 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56736 KB Output is correct
2 Correct 24 ms 56928 KB Output is correct
3 Correct 21 ms 56924 KB Output is correct
4 Correct 21 ms 56920 KB Output is correct
5 Correct 24 ms 57252 KB Output is correct
6 Correct 21 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 22 ms 56668 KB Output is correct
9 Correct 21 ms 56792 KB Output is correct
10 Runtime error 55 ms 115016 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 56668 KB Output is correct
2 Correct 21 ms 56664 KB Output is correct
3 Correct 22 ms 56668 KB Output is correct
4 Correct 23 ms 56872 KB Output is correct
5 Correct 21 ms 56664 KB Output is correct
6 Correct 600 ms 184148 KB Output is correct
7 Runtime error 365 ms 302936 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -