Submission #1168344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168344		Jawad_Akbar_JJ	Triumphal arch (POI13_luk)	C++20	20 / 100	514 ms	17420 KiB

luk

#include <iostream>
#include <vector>

using namespace std;
vector<int> nei[300005];

int dfs(int u, int p, int md){
	vector<int> vec;
	int l = -1, r = 0, cnt = 0;
	for (int i : nei[u])
		if (i != p)
			vec.push_back(dfs(i, u, md)), r = max(r, vec.back()), cnt++;
	
	if (cnt >= md)
		return r + cnt - md;
	md -= cnt;
	
	while (l + 1 < r){
		// cout<<u<<" "<<l<<" "<<r<<endl;
		int mid = (l + r) / 2, sm = 0;

		for (int &i : vec)
			sm += max(0, i - mid);
		if (sm <= md)
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin>>n;

	for (int i=1;i<n;i++){
		int a, b;
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	int l = 0, r = n;
	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (dfs(1, 1, mid) == 0)
			r = mid;
		else
			l = mid;
	}
	cout<<r<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10