Submission #209745

#	Time	Username	Problem	Language	Result	Execution time	Memory
209745		kapsel	Triumphal arch (POI13_luk)	C++14	100 / 100	862 ms	26456 KiB

luk

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10