oj.uz

Submission #1055975

# Submission time Handle Problem Language Result Execution time Memory
1055975 2024-08-13T06:54:30 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 6000 ms 624720 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],dp3D[N][15],dpC[N];
int cnt;
int Get(int u,int k){
	int &ret=dp[u][k];
	if(ret) return ret;
	if((int)dp2C[u].size()!=(int)dA[u].size()){
		cnt++;
		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((int)dp3D[w][b-d].size()!=(int)c[w].size()){
						cnt++;
						for(int j=0;j<(int)c[w].size();j++) dp3D[w][b-d].insert(-dfs1(c[w][j],b-d-1));
					}
					if((int)c[w].size()>1){
						dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
						val=min(val,-dp3D[w][b-d].top());
						dp3D[w][b-d].insert(-dfs1(c[w][e-1],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())){
		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 114 ms 362064 KB Output is correct
2 Correct 116 ms 362064 KB Output is correct
3 Correct 112 ms 361952 KB Output is correct
4 Correct 120 ms 361948 KB Output is correct
5 Correct 120 ms 362068 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 559924 KB Output is correct
2 Correct 685 ms 518100 KB Output is correct
3 Correct 1029 ms 624720 KB Output is correct
4 Execution timed out 6070 ms 479316 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 362068 KB Output is correct
2 Correct 122 ms 362072 KB Output is correct
3 Correct 120 ms 362064 KB Output is correct
4 Correct 121 ms 362068 KB Output is correct
5 Correct 121 ms 362064 KB Output is correct
6 Correct 121 ms 362068 KB Output is correct
7 Correct 122 ms 362064 KB Output is correct
8 Correct 123 ms 362044 KB Output is correct
9 Correct 120 ms 362104 KB Output is correct
10 Correct 119 ms 362068 KB Output is correct
11 Correct 123 ms 362376 KB Output is correct
12 Correct 120 ms 362068 KB Output is correct
13 Correct 123 ms 362068 KB Output is correct

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 362068 KB Output is correct
2 Correct 122 ms 362072 KB Output is correct
3 Correct 120 ms 362064 KB Output is correct
4 Correct 121 ms 362068 KB Output is correct
5 Correct 121 ms 362064 KB Output is correct
6 Correct 121 ms 362068 KB Output is correct
7 Correct 122 ms 362064 KB Output is correct
8 Correct 123 ms 362044 KB Output is correct
9 Correct 120 ms 362104 KB Output is correct
10 Correct 119 ms 362068 KB Output is correct
11 Correct 123 ms 362376 KB Output is correct
12 Correct 120 ms 362068 KB Output is correct
13 Correct 123 ms 362068 KB Output is correct
14 Correct 125 ms 362836 KB Output is correct
15 Correct 121 ms 362828 KB Output is correct
16 Correct 122 ms 362832 KB Output is correct
17 Correct 130 ms 362888 KB Output is correct
18 Correct 122 ms 362832 KB Output is correct
19 Correct 126 ms 362832 KB Output is correct
20 Correct 122 ms 362892 KB Output is correct
21 Correct 124 ms 362484 KB Output is correct
22 Correct 121 ms 362020 KB Output is correct
23 Correct 126 ms 363600 KB Output is correct
24 Correct 119 ms 363172 KB Output is correct
25 Incorrect 125 ms 363732 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 391844 KB Output is correct
2 Correct 243 ms 393220 KB Output is correct
3 Correct 225 ms 391352 KB Output is correct
4 Correct 232 ms 392276 KB Output is correct
5 Correct 218 ms 389488 KB Output is correct
6 Correct 222 ms 390228 KB Output is correct
7 Correct 273 ms 395092 KB Output is correct
8 Correct 147 ms 377936 KB Output is correct
9 Correct 301 ms 400976 KB Output is correct
10 Correct 202 ms 385208 KB Output is correct
11 Correct 154 ms 371536 KB Output is correct
12 Correct 154 ms 376912 KB Output is correct
13 Correct 121 ms 362072 KB Output is correct
14 Correct 146 ms 362068 KB Output is correct
15 Correct 305 ms 395344 KB Output is correct
16 Correct 185 ms 386312 KB Output is correct
17 Correct 181 ms 386516 KB Output is correct
18 Correct 182 ms 386392 KB Output is correct
19 Correct 177 ms 394064 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 362068 KB Output is correct
2 Correct 122 ms 362072 KB Output is correct
3 Correct 120 ms 362064 KB Output is correct
4 Correct 121 ms 362068 KB Output is correct
5 Correct 121 ms 362064 KB Output is correct
6 Correct 121 ms 362068 KB Output is correct
7 Correct 122 ms 362064 KB Output is correct
8 Correct 123 ms 362044 KB Output is correct
9 Correct 120 ms 362104 KB Output is correct
10 Correct 119 ms 362068 KB Output is correct
11 Correct 123 ms 362376 KB Output is correct
12 Correct 120 ms 362068 KB Output is correct
13 Correct 123 ms 362068 KB Output is correct
14 Correct 125 ms 362836 KB Output is correct
15 Correct 121 ms 362828 KB Output is correct
16 Correct 122 ms 362832 KB Output is correct
17 Correct 130 ms 362888 KB Output is correct
18 Correct 122 ms 362832 KB Output is correct
19 Correct 126 ms 362832 KB Output is correct
20 Correct 122 ms 362892 KB Output is correct
21 Correct 124 ms 362484 KB Output is correct
22 Correct 121 ms 362020 KB Output is correct
23 Correct 126 ms 363600 KB Output is correct
24 Correct 119 ms 363172 KB Output is correct
25 Incorrect 125 ms 363732 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 114 ms 362064 KB Output is correct
2 Correct 116 ms 362064 KB Output is correct
3 Correct 112 ms 361952 KB Output is correct
4 Correct 120 ms 361948 KB Output is correct
5 Correct 120 ms 362068 KB Output is correct
6 Correct 1074 ms 559924 KB Output is correct
7 Correct 685 ms 518100 KB Output is correct
8 Correct 1029 ms 624720 KB Output is correct
9 Execution timed out 6070 ms 479316 KB Time limit exceeded
10 Halted 0 ms 0 KB -