oj.uz

답안 #1056218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056218 2024-08-13T08:17:43 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
10 / 25
 809 ms 658064 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];
int sz[N],in[N],inv[N],out[N],C,ctop[N];
vector<int> dp[N],dp2[N];
int dp3[N][15],dp4[N][15];
vector<int> g[N],c[N],dL[N];
vector<int> dA[N],idxsubA[N];
vector<int> up[N],invup[N];
void dfs0(int u){
	L[dep[u]]=u;
	dL[dep[u]].push_back(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);
	}
	sz[u]=1;
	for(int v: g[u]) if(p[u]!=v){
		dep[v]=dep[u]+1;
		p[v]=u;
		c[u].push_back(v);
		dfs0(v);
		sz[u]+=sz[v];
	}
}
void dfsH(int u,int t){
	in[u]=++C;
	inv[in[u]]=u;
	ctop[u]=t;
	int idx=0;
	for(int v: c[u]){
		q[v]=++idx;
		if(v==c[u][0]) dfsH(v,t);
		else dfsH(v,v);
	}
	out[u]=C;
}
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];
int dfs1(int u,int d){
	int &ret=dp3[u][d];
	if(ret) return ret;
	ret=dp[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 u=1;u<=n;u++){
		for(int &v: c[u]) if(sz[v]>sz[c[u][0]]) swap(v,c[u][0]);
	}
	dfsH(r,r);
	for(int i=1;i<=n;i++){
		dp[i].resize(c[i].size()+1);
		dp2[i].resize(dA[i].size());
	}
	for(int i=1;i<=n;i++){
		int u=i;
		while(u){
			up[i].push_back(u);
			invup[u].push_back(i);
			u=p[ctop[u]];
		}
	}
	for(int D=n;D>=0;D--){
		for(int u: dL[D]){
			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,dp[w][e]);
					if(d<b){
						if((int)dp3D[w][b-d].size()!=(int)c[w].size()){
							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]);
			}
			for(int k=0;k<=(int)c[u].size();k++){
				int &ret=dp[u][k];
				if(dA[u].empty()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
					if(k&&idxsubA[c[u][k-1]].empty()) ret=dp[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]);
					}
				}
			}
		}
	}
	cout<<dp[r][0];
	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 367700 KB Output is correct
2 Correct 47 ms 367708 KB Output is correct
3 Correct 47 ms 367708 KB Output is correct
4 Correct 47 ms 367696 KB Output is correct
5 Correct 47 ms 367700 KB Output is correct

Subtask #2
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 750 ms 594296 KB Output is correct
2 Correct 809 ms 618576 KB Output is correct
3 Incorrect 730 ms 658064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 374096 KB Output is correct
2 Correct 49 ms 374100 KB Output is correct
3 Correct 52 ms 374112 KB Output is correct
4 Correct 47 ms 374108 KB Output is correct
5 Correct 50 ms 374100 KB Output is correct
6 Correct 48 ms 374056 KB Output is correct
7 Correct 47 ms 374100 KB Output is correct
8 Correct 47 ms 372052 KB Output is correct
9 Correct 53 ms 367912 KB Output is correct
10 Correct 47 ms 374104 KB Output is correct
11 Correct 47 ms 374304 KB Output is correct
12 Correct 49 ms 374116 KB Output is correct
13 Correct 48 ms 374100 KB Output is correct

Subtask #4
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 374096 KB Output is correct
2 Correct 49 ms 374100 KB Output is correct
3 Correct 52 ms 374112 KB Output is correct
4 Correct 47 ms 374108 KB Output is correct
5 Correct 50 ms 374100 KB Output is correct
6 Correct 48 ms 374056 KB Output is correct
7 Correct 47 ms 374100 KB Output is correct
8 Correct 47 ms 372052 KB Output is correct
9 Correct 53 ms 367912 KB Output is correct
10 Correct 47 ms 374104 KB Output is correct
11 Correct 47 ms 374304 KB Output is correct
12 Correct 49 ms 374116 KB Output is correct
13 Correct 48 ms 374100 KB Output is correct
14 Correct 50 ms 374864 KB Output is correct
15 Correct 52 ms 375096 KB Output is correct
16 Correct 51 ms 374864 KB Output is correct
17 Correct 49 ms 375080 KB Output is correct
18 Correct 52 ms 374868 KB Output is correct
19 Correct 49 ms 374864 KB Output is correct
20 Correct 51 ms 375136 KB Output is correct
21 Correct 50 ms 372564 KB Output is correct
22 Correct 47 ms 367916 KB Output is correct
23 Correct 54 ms 375632 KB Output is correct
24 Correct 50 ms 375224 KB Output is correct
25 Incorrect 56 ms 375892 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 411248 KB Output is correct
2 Correct 172 ms 412692 KB Output is correct
3 Correct 161 ms 410504 KB Output is correct
4 Correct 174 ms 412112 KB Output is correct
5 Correct 145 ms 408524 KB Output is correct
6 Correct 166 ms 410140 KB Output is correct
7 Correct 203 ms 414704 KB Output is correct
8 Correct 118 ms 395724 KB Output is correct
9 Correct 259 ms 420944 KB Output is correct
10 Correct 209 ms 413776 KB Output is correct
11 Correct 133 ms 396624 KB Output is correct
12 Correct 119 ms 395388 KB Output is correct
13 Correct 48 ms 367916 KB Output is correct
14 Correct 46 ms 367700 KB Output is correct
15 Correct 230 ms 414960 KB Output is correct
16 Correct 112 ms 404772 KB Output is correct
17 Correct 108 ms 404824 KB Output is correct
18 Correct 113 ms 404556 KB Output is correct
19 Correct 244 ms 451408 KB Output is correct

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 374096 KB Output is correct
2 Correct 49 ms 374100 KB Output is correct
3 Correct 52 ms 374112 KB Output is correct
4 Correct 47 ms 374108 KB Output is correct
5 Correct 50 ms 374100 KB Output is correct
6 Correct 48 ms 374056 KB Output is correct
7 Correct 47 ms 374100 KB Output is correct
8 Correct 47 ms 372052 KB Output is correct
9 Correct 53 ms 367912 KB Output is correct
10 Correct 47 ms 374104 KB Output is correct
11 Correct 47 ms 374304 KB Output is correct
12 Correct 49 ms 374116 KB Output is correct
13 Correct 48 ms 374100 KB Output is correct
14 Correct 50 ms 374864 KB Output is correct
15 Correct 52 ms 375096 KB Output is correct
16 Correct 51 ms 374864 KB Output is correct
17 Correct 49 ms 375080 KB Output is correct
18 Correct 52 ms 374868 KB Output is correct
19 Correct 49 ms 374864 KB Output is correct
20 Correct 51 ms 375136 KB Output is correct
21 Correct 50 ms 372564 KB Output is correct
22 Correct 47 ms 367916 KB Output is correct
23 Correct 54 ms 375632 KB Output is correct
24 Correct 50 ms 375224 KB Output is correct
25 Incorrect 56 ms 375892 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 367700 KB Output is correct
2 Correct 47 ms 367708 KB Output is correct
3 Correct 47 ms 367708 KB Output is correct
4 Correct 47 ms 367696 KB Output is correct
5 Correct 47 ms 367700 KB Output is correct
6 Correct 750 ms 594296 KB Output is correct
7 Correct 809 ms 618576 KB Output is correct
8 Incorrect 730 ms 658064 KB Output isn't correct
9 Halted 0 ms 0 KB -