oj.uz

Submission #987919

# Submission time Handle Problem Language Result Execution time Memory
987919 2024-05-23T19:13:15 Z Kevin_Jao Triumphal arch (POI13_luk) C++17
100 / 100
 1095 ms 31568 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 6 ms 9972 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9668 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10332 KB Output is correct
2 Correct 11 ms 10368 KB Output is correct
3 Correct 7 ms 10332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11356 KB Output is correct
2 Correct 23 ms 12264 KB Output is correct
3 Correct 14 ms 11356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 14888 KB Output is correct
2 Correct 72 ms 16980 KB Output is correct
3 Correct 36 ms 15156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 20060 KB Output is correct
2 Correct 327 ms 25880 KB Output is correct
3 Correct 167 ms 20380 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 25424 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 25392 KB Output is correct
2 Correct 977 ms 31568 KB Output is correct
3 Correct 213 ms 25680 KB Output is correct