oj.uz

Submission #106087

# Submission time Handle Problem Language Result Execution time Memory
106087 2019-04-16T13:39:26 Z Adhyyan1252 Triumphal arch (POI13_luk) C++11
100 / 100
 1392 ms 26488 KB 
#include<bits/stdc++.h>

using namespace std;
//6 42
vector<vector<int> > g;


int check(int x, int cur=0, int par = -1){
	int sum = 0;
	for(int i: g[cur]){
		if(i == par) continue;
		sum += check(x, i, cur)+1;
	}
	sum -= x;
	sum = max(sum, 0);
	return sum;
}

int main(){
	int n; cin>>n;
	g.resize(n);
	for(int i = 0; i < n-1; i++){
		int u, v; cin>>u>>v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int low = 1, high = n-1, mid;
	while(low < high){
		mid = (low + high)/2;
		if(check(mid) == 0){
			high = mid;
		}else{
			low = mid+1;
		}
	}
	mid = (low + high)/2;
	cout<<mid<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 128 KB Output is correct
3 Correct 3 ms 356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 428 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1064 KB Output is correct
2 Correct 17 ms 1240 KB Output is correct
3 Correct 13 ms 1092 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2328 KB Output is correct
2 Correct 52 ms 3188 KB Output is correct
3 Correct 38 ms 2456 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 7156 KB Output is correct
2 Correct 242 ms 9080 KB Output is correct
3 Correct 95 ms 7544 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 14248 KB Output is correct
2 Correct 981 ms 18816 KB Output is correct
3 Correct 399 ms 14876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 21340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 21296 KB Output is correct
2 Correct 1318 ms 26488 KB Output is correct
3 Correct 542 ms 22264 KB Output is correct