Submission #1129887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129887		8pete8	Papričice (COCI20_papricice)	C++20	110 / 110	223 ms	70872 KiB

papricice

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include <cstdint>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mod=1e9+7,mxn=2e5+5,lg=30,inf=1e18,minf=-1e18;
int n,q,c;
vector<int>adj[mxn+10];
int sz[mxn+10],ans=inf,dp[mxn+10][2],up[mxn+10][lg+1];
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p)getsz(i,cur),sz[cur]+=sz[i];}
int get(int x,int y,int z){return max({abs(x-y),abs(x-z),abs(y-z)});}
void dfs(int cur,int p){
	dp[cur][0]=minf,dp[cur][1]=inf;
	for(int i=1;i<=lg;i++)up[cur][i]=up[up[cur][i-1]][i-1];
	for(auto i:adj[cur])if(i!=p){
		up[i][0]=cur;
		dfs(i,cur);
		for(int k=0;k<2;k++)for(int j=0;j<2;j++)ans=min(ans,get(dp[cur][k],dp[i][j],n-dp[cur][k]-dp[i][j]));
		dp[cur][0]=max(dp[cur][0],dp[i][0]);
		dp[cur][1]=min(dp[cur][1],dp[i][1]);
	}
	if(sz[cur]>(n/3))dp[cur][1]=min(dp[cur][1],sz[cur]);
	else dp[cur][0]=max(dp[cur][0],sz[cur]);
	int x=cur;
	for(int i=lg;i>=0;i--)if(sz[up[x][i]]-sz[cur]<(n-sz[cur])/2)x=up[x][i];
	ans=min(ans,get(sz[cur],sz[x]-sz[cur],n-sz[x]));
	x=up[x][0];
	ans=min(ans,get(sz[cur],sz[x]-sz[cur],n-sz[x]));
}
int32_t main(){
	fastio
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	getsz(1,-1);
	for(int i=0;i<=lg;i++)up[1][i]=1;
	dfs(1,-1);
	cout<<ans;
}
/*
keep closest value to n/3?
2 cases ->same subtree and diff subtree
*/

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60