oj.uz

Submission #1055904

# Submission time Handle Problem Language Result Execution time Memory
1055904 2024-08-13T06:27:38 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
6 / 25
 6000 ms 181108 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){
	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){
	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 20 ms 56776 KB Output is correct
3 Correct 19 ms 56664 KB Output is correct
4 Correct 20 ms 56668 KB Output is correct
5 Correct 19 ms 56692 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 181108 KB Output is correct
2 Correct 426 ms 176880 KB Output is correct
3 Correct 637 ms 179536 KB Output is correct
4 Execution timed out 6038 ms 152540 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 56924 KB Output is correct
2 Correct 21 ms 56924 KB Output is correct
3 Correct 20 ms 56924 KB Output is correct
4 Correct 23 ms 56912 KB Output is correct
5 Correct 21 ms 56924 KB Output is correct
6 Correct 23 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 20 ms 56668 KB Output is correct
9 Correct 20 ms 56832 KB Output is correct
10 Correct 21 ms 56872 KB Output is correct
11 Correct 21 ms 56920 KB Output is correct
12 Correct 20 ms 56844 KB Output is correct
13 Correct 21 ms 56816 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 56924 KB Output is correct
2 Correct 21 ms 56924 KB Output is correct
3 Correct 20 ms 56924 KB Output is correct
4 Correct 23 ms 56912 KB Output is correct
5 Correct 21 ms 56924 KB Output is correct
6 Correct 23 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 20 ms 56668 KB Output is correct
9 Correct 20 ms 56832 KB Output is correct
10 Correct 21 ms 56872 KB Output is correct
11 Correct 21 ms 56920 KB Output is correct
12 Correct 20 ms 56844 KB Output is correct
13 Correct 21 ms 56816 KB Output is correct
14 Correct 22 ms 57692 KB Output is correct
15 Correct 23 ms 57692 KB Output is correct
16 Correct 23 ms 57624 KB Output is correct
17 Correct 23 ms 57684 KB Output is correct
18 Correct 22 ms 57692 KB Output is correct
19 Correct 23 ms 57612 KB Output is correct
20 Correct 23 ms 57688 KB Output is correct
21 Correct 22 ms 57336 KB Output is correct
22 Correct 21 ms 56756 KB Output is correct
23 Correct 23 ms 57388 KB Output is correct
24 Correct 23 ms 57692 KB Output is correct
25 Incorrect 24 ms 57520 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 85844 KB Output is correct
2 Correct 109 ms 87888 KB Output is correct
3 Correct 108 ms 86368 KB Output is correct
4 Correct 108 ms 87528 KB Output is correct
5 Correct 106 ms 86864 KB Output is correct
6 Correct 110 ms 87996 KB Output is correct
7 Correct 114 ms 86460 KB Output is correct
8 Correct 63 ms 72784 KB Output is correct
9 Correct 140 ms 85884 KB Output is correct
10 Correct 75 ms 79696 KB Output is correct
11 Correct 53 ms 66132 KB Output is correct
12 Correct 53 ms 71504 KB Output is correct
13 Correct 20 ms 56664 KB Output is correct
14 Correct 20 ms 56668 KB Output is correct
15 Correct 136 ms 81492 KB Output is correct
16 Execution timed out 6063 ms 79684 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 56924 KB Output is correct
2 Correct 21 ms 56924 KB Output is correct
3 Correct 20 ms 56924 KB Output is correct
4 Correct 23 ms 56912 KB Output is correct
5 Correct 21 ms 56924 KB Output is correct
6 Correct 23 ms 56924 KB Output is correct
7 Correct 21 ms 56924 KB Output is correct
8 Correct 20 ms 56668 KB Output is correct
9 Correct 20 ms 56832 KB Output is correct
10 Correct 21 ms 56872 KB Output is correct
11 Correct 21 ms 56920 KB Output is correct
12 Correct 20 ms 56844 KB Output is correct
13 Correct 21 ms 56816 KB Output is correct
14 Correct 22 ms 57692 KB Output is correct
15 Correct 23 ms 57692 KB Output is correct
16 Correct 23 ms 57624 KB Output is correct
17 Correct 23 ms 57684 KB Output is correct
18 Correct 22 ms 57692 KB Output is correct
19 Correct 23 ms 57612 KB Output is correct
20 Correct 23 ms 57688 KB Output is correct
21 Correct 22 ms 57336 KB Output is correct
22 Correct 21 ms 56756 KB Output is correct
23 Correct 23 ms 57388 KB Output is correct
24 Correct 23 ms 57692 KB Output is correct
25 Incorrect 24 ms 57520 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 21 ms 56668 KB Output is correct
2 Correct 20 ms 56776 KB Output is correct
3 Correct 19 ms 56664 KB Output is correct
4 Correct 20 ms 56668 KB Output is correct
5 Correct 19 ms 56692 KB Output is correct
6 Correct 660 ms 181108 KB Output is correct
7 Correct 426 ms 176880 KB Output is correct
8 Correct 637 ms 179536 KB Output is correct
9 Execution timed out 6038 ms 152540 KB Time limit exceeded
10 Halted 0 ms 0 KB -