Submission #1168225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168225		ghammazhassan	Triumphal arch (POI13_luk)	C++20	0 / 100	826 ms	39192 KiB

luk

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define fi first
#define se second
const int N=3e5+5;
const int M=1e9+7;
const int LOG = 20;
int n , m , k , c , d , t=1 , q=1 , x , y , p[N] , l , r;
vector<vector<int>>a(N);

int bp(int x,int y){
	x=x%M;
	if (y==0)return 1;
	if (y==1)return x;
	int r=bp(x*x,y/2);
	if (y%2)r*=x;
	r%=M;
	return r;
}
int inv(int x){
	return bp(x,M-2);
}

void solve()
{	
	cin >> n;
	for (int i=0;i<n-1;i++){
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	vector<int>vi(n+1);
	vector<int>ch(n+1);
	vector<int>di(n+1);
	vector<int>d(n+1);
	queue<int>o;
	o.push(1);
	vi[1]=1;
	p[1]=1;
	vector<int>dy;
	while (!o.empty()){
		int h=o.front();
		o.pop();
		for (int i:a[h]){
			if (vi[i])continue;
			vi[i]=1;
			ch[h]++;
			p[i]=h;
			d[i]=d[h]+1;
			o.push(i);
		}
	}
	int l=1;
	int h=n-1;
	int m=(l+h)/2;
	while (l<h){
		vector<int>dp(n+1,m);
		bool f=1;
		vector<int>vi(n+1);
		o.push(1);
		vi[1]=1;
		while (!o.empty()){
			int h=o.front();
			o.pop();
			dp[h]-=ch[h];
			for (int i:a[h]){
				if (vi[i])continue;
				vi[i]=1;
				o.push(i);
			}
		}
		vector<int>k;
		for (int i=1;i<=n;i++){
			if (ch[i]==0)k.push_back(i);
		}

		for (int i:k){
			x=i;
			while (x!=1){
				if (dp[x]<0)dp[p[x]]+=dp[x];
				x=p[x];
			}
		}
		if (dp[1]<0){
			l=m+1;
		}
		else{
			h=m;
		}
		m=(l+h)/2;
	}
	cout << m << endl;

}
signed main()	
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed<<setprecision(9);
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
    	solve();
    	q++;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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