Submission #106087

#	Time	Username	Problem	Language	Result	Execution time	Memory
106087		Adhyyan1252	Triumphal arch (POI13_luk)	C++11	100 / 100	1392 ms	26488 KiB

luk

#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 / 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