oj.uz

Submission #1056193

# Submission time Handle Problem Language Result Execution time Memory
1056193 2024-08-13T08:10:31 Z 김은성(#11066) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 12 ms 48476 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[300009];
int par[300009], sp[20][300009], anc[300009], depth[300009], height[300009], mnv[300009];	//anc[v]: a-th ancestor of v
vector<int> child[300009];
int sz0[300009], sz[300009], mn[300009];	//sz[v]: number of a-th decendants of v, mn[v]: minimum value among self and 1~b-th dec, infinity if height >= a 
bool cha[300009], chb0[300009], chb1[300009];
bool tch[300009];
queue<int> q;	//impossible b positions
void settree(int v){
	height[v] = 0;
	for(int u: graph[v]){
		if(par[v] == u)
			continue;
		par[u] = v;
		child[v].push_back(u);
		depth[u] = depth[v] + 1;
		settree(u);
		height[v] = max(height[v], height[u] + 1);
	}
}
int getmin(int v, int d){
	if(d==0)
		return v;
	int ret = v;
	for(int u: child[v]){
		ret = min(ret, getmin(u, d-1));
	}
	return ret;
}
void updatecircle(int v, int d){
	tch[v] = 1;
	if(!cha[v]){
		cha[v] = 1;
		sz[anc[v]]--;
		if(!sz[anc[v]] && !chb1[anc[v]]){
			chb1[anc[v]] = 1;
			q.push(anc[v]);
		}
	}
	if(d==0)
		return;
	for(int u: graph[v]){
		if(!tch[u])
			updatecircle(u, d-1);
	}
}
void updatedescendant(int v, int d){
	tch[v] = 1;
	if(d==0)
		return;
	for(int u: child[v]){
		if(!tch[u]){
			updatedescendant(u, d-1);
			if(!cha[u]){
				cha[u] = 1;
				sz[anc[u]]--;
				//printf("v=%d sz[%d]=%d\n", v, anc[v], sz[anc[v]]);
				if(!sz[anc[u]] && !chb1[anc[u]]){
					chb1[anc[u]] = 1;
					q.push(anc[u]);
				}
			}
		}
	}
}
int main(){
	int n, r, a, b, i, j, u, v;
	scanf("%d %d %d %d", &n, &r, &a, &b);
	if(a<=b){
		printf("1\n");
		return 0;
	}
	assert(n <= 300);
	for(i=1; i<n; i++){
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	settree(r);
	for(i=1; i<=n; i++){
		if(height[i] >= a)
			mn[i] = i;
		else
			mn[i] = getmin(i, b);
	}
	for(i=1; i<=n; i++)
		sp[0][i] = par[i];
	for(i=1; i<20; i++){
		for(j=1; j<=n; j++){
			sp[i][j] = sp[i-1][sp[i-1][j]];
		}
	}
	for(i=1; i<=n; i++){
		int cur = a;
		int v = i;
		for(j=19; j>=0; j--){
			if(cur >= (1<<j)){
				cur -= (1<<j);
				v = sp[j][v];
			}
		}
		anc[i] = v;
		//printf("i=%d anc=%d\n", i, v);
		sz0[v]++;
	}
	int lo = 1, hi = n, mid;
	while(lo < hi){
		mid = (lo+hi)/2;
		memset(cha, 0 ,sizeof(cha));
		for(i=1; i<=n; i++){
			sz[i] = sz0[i];
			chb0[i] = chb1[i] = 0;
			if(mn[i] <= mid){
				if(height[i] < a)
					chb1[i] = 1;
				else
					chb0[i] = 1;
				q.push(i);
			}
		}
		//printf("mid=%d\n", mid);
		while(!q.empty()){
			int v = q.front();
			//printf("v=%d\n", v);
			q.pop();
			memset(tch, 0, sizeof(tch));
			if(chb1[v])
				updatecircle(v, b);
			else
				updatedescendant(v, b);
		}
		if(chb1[r])
			hi = mid;
		else
			lo = mid+1;
	}
	printf("%d\n", lo);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d %d %d %d", &n, &r, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17500 KB Output is correct
2 Correct 3 ms 17596 KB Output is correct
3 Correct 2 ms 17608 KB Output is correct
4 Correct 2 ms 17500 KB Output is correct
5 Correct 2 ms 17500 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 35440 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 48476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 48476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 35420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 48476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17500 KB Output is correct
2 Correct 3 ms 17596 KB Output is correct
3 Correct 2 ms 17608 KB Output is correct
4 Correct 2 ms 17500 KB Output is correct
5 Correct 2 ms 17500 KB Output is correct
6 Runtime error 12 ms 35440 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -