oj.uz

Submission #1055928

# Submission time Handle Problem Language Result Execution time Memory
1055928 2024-08-13T06:38:59 Z 김은성(#11066) Summer Driving (CCO24_day1problem3) C++17
5 / 25
 236 ms 93148 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[1000009];
int par[1000009], depth[1000009];
vector<int> child[1000009];
int pos[1000009];
void settree(int v){
	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);
	}
}
int main(){
	int n, r, a, b, i, u, v;
	scanf("%d %d %d %d", &n, &r, &a, &b);
	assert(1 <= r && r <= n && 1<=a && a<=n && 1<=b && b<=n);
	for(i=1; i<n; i++){
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	settree(r);
	int k, l;
	if(a >= n){
		pos[min(n, b+1)]--;
		pos[0]++;
	}
	for(k=1; a*k<n; k++){
		if(a*k + k*b + a >= n){
			if(min(n, a*k + k*b + b + 1) < 0){
				printf("1\n");
				return 0;
			}
			pos[min(n, a*k + k*b + b + 1)]--;
			if(max(n-a, a*k-b) > n){
				printf("1\n");
				return 0;
			}
			pos[max(n-a, a*k-b)]++;
		}
		if(min(n, a*k + (k-1)*b) < 0){
			printf("1\n");
				return 0;
		}
		pos[min(n, a*k + (k-1)*b)]--;
		if(max(0, a*k-b) > n){
			printf("1\n");
			return 0;
		}
		pos[max(0, a*k-b)]++;
	}
	for(i=1; i<n; i++){
		pos[i] += pos[i-1];
	}
	for(i=1; i<=n; i++){
		if(pos[depth[i]] > 0){
			printf("%d\n", i);
			return 0;
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 65512 KB Output is correct
2 Correct 141 ms 65364 KB Output is correct
3 Correct 206 ms 66132 KB Output is correct
4 Correct 154 ms 66052 KB Output is correct
5 Correct 15 ms 47208 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 93068 KB Output is correct
2 Correct 203 ms 93008 KB Output is correct
3 Correct 157 ms 92928 KB Output is correct
4 Correct 155 ms 92884 KB Output is correct
5 Correct 209 ms 91532 KB Output is correct
6 Correct 220 ms 92804 KB Output is correct
7 Correct 194 ms 92856 KB Output is correct
8 Correct 212 ms 93148 KB Output is correct
9 Correct 229 ms 90708 KB Output is correct
10 Correct 215 ms 93104 KB Output is correct
11 Correct 236 ms 93012 KB Output is correct
12 Correct 18 ms 47196 KB Output is correct

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 47704 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 17 ms 47704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

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

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 47704 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 166 ms 65512 KB Output is correct
2 Correct 141 ms 65364 KB Output is correct
3 Correct 206 ms 66132 KB Output is correct
4 Correct 154 ms 66052 KB Output is correct
5 Correct 15 ms 47208 KB Output is correct
6 Correct 188 ms 93068 KB Output is correct
7 Correct 203 ms 93008 KB Output is correct
8 Correct 157 ms 92928 KB Output is correct
9 Correct 155 ms 92884 KB Output is correct
10 Correct 209 ms 91532 KB Output is correct
11 Correct 220 ms 92804 KB Output is correct
12 Correct 194 ms 92856 KB Output is correct
13 Correct 212 ms 93148 KB Output is correct
14 Correct 229 ms 90708 KB Output is correct
15 Correct 215 ms 93104 KB Output is correct
16 Correct 236 ms 93012 KB Output is correct
17 Correct 18 ms 47196 KB Output is correct
18 Incorrect 17 ms 47704 KB Output isn't correct
19 Halted 0 ms 0 KB -