oj.uz

답안 #1055927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055927 2024-08-13T06:38:45 Z d(#11110) Summer Driving (CCO24_day1problem3) C++17
6 / 25
 6000 ms 601680 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];
int Get(int u,int k){
	int &ret=dp[u][k];
	if(ret) return ret;
	if((int)dp2C[u].size()!=(int)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){
					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]);
		}
	}
	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(dp2[u][i]);
			}
		}
		ret=dp2C[u].top();
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 343120 KB Output is correct
2 Correct 115 ms 343192 KB Output is correct
3 Correct 111 ms 343108 KB Output is correct
4 Correct 114 ms 343140 KB Output is correct
5 Correct 113 ms 343120 KB Output is correct

Subtask #2
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1066 ms 537368 KB Output is correct
2 Correct 662 ms 495632 KB Output is correct
3 Correct 992 ms 601680 KB Output is correct
4 Execution timed out 6068 ms 459708 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 343444 KB Output is correct
2 Correct 115 ms 343396 KB Output is correct
3 Correct 115 ms 343380 KB Output is correct
4 Correct 115 ms 343368 KB Output is correct
5 Correct 120 ms 343380 KB Output is correct
6 Correct 126 ms 343432 KB Output is correct
7 Correct 135 ms 343376 KB Output is correct
8 Correct 116 ms 343376 KB Output is correct
9 Correct 124 ms 343124 KB Output is correct
10 Correct 108 ms 343376 KB Output is correct
11 Correct 110 ms 343544 KB Output is correct
12 Correct 108 ms 343124 KB Output is correct
13 Correct 125 ms 343288 KB Output is correct

Subtask #4
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 343444 KB Output is correct
2 Correct 115 ms 343396 KB Output is correct
3 Correct 115 ms 343380 KB Output is correct
4 Correct 115 ms 343368 KB Output is correct
5 Correct 120 ms 343380 KB Output is correct
6 Correct 126 ms 343432 KB Output is correct
7 Correct 135 ms 343376 KB Output is correct
8 Correct 116 ms 343376 KB Output is correct
9 Correct 124 ms 343124 KB Output is correct
10 Correct 108 ms 343376 KB Output is correct
11 Correct 110 ms 343544 KB Output is correct
12 Correct 108 ms 343124 KB Output is correct
13 Correct 125 ms 343288 KB Output is correct
14 Correct 115 ms 344112 KB Output is correct
15 Correct 115 ms 344148 KB Output is correct
16 Correct 130 ms 344032 KB Output is correct
17 Correct 117 ms 344144 KB Output is correct
18 Correct 114 ms 344144 KB Output is correct
19 Correct 119 ms 343972 KB Output is correct
20 Correct 116 ms 344140 KB Output is correct
21 Correct 119 ms 343740 KB Output is correct
22 Correct 113 ms 343108 KB Output is correct
23 Correct 123 ms 344768 KB Output is correct
24 Correct 126 ms 344272 KB Output is correct
25 Incorrect 123 ms 345108 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 372052 KB Output is correct
2 Correct 236 ms 373972 KB Output is correct
3 Correct 218 ms 372064 KB Output is correct
4 Correct 216 ms 373172 KB Output is correct
5 Correct 216 ms 370180 KB Output is correct
6 Correct 204 ms 371144 KB Output is correct
7 Correct 244 ms 375892 KB Output is correct
8 Correct 148 ms 358736 KB Output is correct
9 Correct 299 ms 381784 KB Output is correct
10 Correct 167 ms 366420 KB Output is correct
11 Correct 159 ms 352692 KB Output is correct
12 Correct 148 ms 358228 KB Output is correct
13 Correct 114 ms 343200 KB Output is correct
14 Correct 114 ms 343120 KB Output is correct
15 Correct 293 ms 376640 KB Output is correct
16 Execution timed out 6044 ms 366384 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 343444 KB Output is correct
2 Correct 115 ms 343396 KB Output is correct
3 Correct 115 ms 343380 KB Output is correct
4 Correct 115 ms 343368 KB Output is correct
5 Correct 120 ms 343380 KB Output is correct
6 Correct 126 ms 343432 KB Output is correct
7 Correct 135 ms 343376 KB Output is correct
8 Correct 116 ms 343376 KB Output is correct
9 Correct 124 ms 343124 KB Output is correct
10 Correct 108 ms 343376 KB Output is correct
11 Correct 110 ms 343544 KB Output is correct
12 Correct 108 ms 343124 KB Output is correct
13 Correct 125 ms 343288 KB Output is correct
14 Correct 115 ms 344112 KB Output is correct
15 Correct 115 ms 344148 KB Output is correct
16 Correct 130 ms 344032 KB Output is correct
17 Correct 117 ms 344144 KB Output is correct
18 Correct 114 ms 344144 KB Output is correct
19 Correct 119 ms 343972 KB Output is correct
20 Correct 116 ms 344140 KB Output is correct
21 Correct 119 ms 343740 KB Output is correct
22 Correct 113 ms 343108 KB Output is correct
23 Correct 123 ms 344768 KB Output is correct
24 Correct 126 ms 344272 KB Output is correct
25 Incorrect 123 ms 345108 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 343120 KB Output is correct
2 Correct 115 ms 343192 KB Output is correct
3 Correct 111 ms 343108 KB Output is correct
4 Correct 114 ms 343140 KB Output is correct
5 Correct 113 ms 343120 KB Output is correct
6 Correct 1066 ms 537368 KB Output is correct
7 Correct 662 ms 495632 KB Output is correct
8 Correct 992 ms 601680 KB Output is correct
9 Execution timed out 6068 ms 459708 KB Time limit exceeded
10 Halted 0 ms 0 KB -