Submission #1168188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168188		UmairAhmadMirza	Triumphal arch (POI13_luk)	C++20	100 / 100	386 ms	25100 KiB

luk

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=3e5+5;
int const mod=1e9+7;

vector<int> adj[N];

int dp[N],n,cur;

void dfs(int node,int par){
	dp[node]=adj[node].size();
	if(par>0)
		dp[node]--;
	dp[node]-=cur;
	for(int i:adj[node])
		if(i!=par){
			dfs(i,node);
			dp[node]+=dp[i];
		}
	dp[node]=max(dp[node],0);
}

bool solve(int k){
	for (int i = 0; i <=n; ++i)
		dp[i]=0;
	cur=k;
	dfs(1,0);
	return (dp[1]==0);
}

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

• 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