Submission #987919

#	Time	Username	Problem	Language	Result	Execution time	Memory
987919		Kevin_Jao	Triumphal arch (POI13_luk)	C++17	100 / 100	1095 ms	31568 KiB

luk

#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<utility>
#include<iomanip>
#include<string.h>
#include<limits.h>
#include<algorithm>
#include<functional>
#include<unordered_map> 
using namespace std;
#define MOD 1000000007
#define int long long
#define ss second
#define ff first
#define endl '\n'
const int mxN=3e5+1;
vector<int> v[mxN],dp(mxN);
void dfs(int a, int p, int k){
	int need=0;
	for(auto node: v[a]){
		if(node!=p){
			dfs(node,a,k);
			need+=dp[node]+1;
		}
	}
	dp[a]=max(need-k,0ll);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n; cin>>n;
	for(int i=1; i<n; i++){
		int a,b; cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int l=0,r=n;
	while(l<=r){
		int m=l+(r-l)/2;
		for(int i=1; i<=n; i++) dp[i]=0;
		dfs(1,1,m);
		if(dp[1]==0) r=m-1;
		else l=m+1;
	}
	cout<<l;
	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