oj.uz

Submission #209745

# Submission time Handle Problem Language Result Execution time Memory
209745 2020-03-15T13:06:22 Z kapsel Triumphal arch (POI13_luk) C++14
100 / 100
 862 ms 26456 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define LL long long 
#define ULL unsigned long long 
#define LD long double 

const int N = 3e5 + 2137;
vector<int> V[N];

int spr(int v, int k, int oj) {
	int n = V[v].size();
	LL w = 0;
	for(int i=0; i<n; i++) {
		int u = V[v][i];
		if(u!=oj) {
			w+=spr(u, k, v)+1;
		}
	}
	return max((LL)0, w-k);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a, b;
	for(int i=1; i<n; i++) {
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	int poc = 0;
	int kon = n;
	while(poc<kon) {
		int sr = (poc+kon) / 2;
		if(!spr(1, sr, -1))
			kon = sr;
		else
			poc = sr + 1;
	}
	cout<<poc;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7420 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 10 ms 7544 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7800 KB Output is correct
2 Correct 16 ms 8056 KB Output is correct
3 Correct 13 ms 7800 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8696 KB Output is correct
2 Correct 42 ms 9592 KB Output is correct
3 Correct 22 ms 8824 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 11876 KB Output is correct
2 Correct 148 ms 13792 KB Output is correct
3 Correct 70 ms 12280 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 16632 KB Output is correct
2 Correct 461 ms 21112 KB Output is correct
3 Correct 160 ms 17144 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 21244 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 21240 KB Output is correct
2 Correct 801 ms 26456 KB Output is correct
3 Correct 298 ms 22136 KB Output is correct