Submission #403577

#	Time	Username	Problem	Language	Result	Execution time	Memory
403577		NurstanDuisengaliev	Papričice (COCI20_papricice)	C++14	50 / 110	1087 ms	16476 KiB

papricice

// Nurstan Duisengaliev(REALBOY)
// Respa Gold_2022
// IZHO GOLD_2022
// IOI_2022 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")*/                   
      
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
 
using namespace std;
 
const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 1;
int n;
vector <int> g[N]; 
int tin[N], tout[N], timer = 0, sz[N];
void PreCalc (int v, int p) {
	tin[v] = ++ timer;
	sz[v] = 1;
	for (auto to : g[v]) {
		if (to != p) {
			PreCalc (to, v);
			sz[v] += sz[to];
		}
	}
	tout[v] = timer;
}
bool used[N];
int x;
int mini = mod;
bool anc (int v, int u) {
	return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
void Dfs2 (int v, int p, int o) {
	if (v != 1) {
		int y = sz[v] - (anc (v, o) ? x : 0);
		int z = n - x - y;
		mini = min (mini, max ({x, y, z}) - min ({x, y, z}));	
	}
	for (auto to : g[v]) {
		if (!used[to] && to != p) Dfs2 (to, v, o);
	}
}
void Dfs1 (int v, int p) {
	if (v != 1) {
		used[v] = 1;
		x = sz[v];
		Dfs2 (1, -1, v);
		used[v] = 0;
	}
	for (auto to : g[v]) {
		if (to != p) Dfs1 (to, v);
	}
}
void solve () {
	cin >> n;
	for (int i = 1; i < n; i ++) {
		int l, r;
		cin >> l >> r;
		g[l].pb (r);
		g[r].pb (l);
	}
	PreCalc (1, -1);
	Dfs1 (1, -1);
	cout << mini;
}   	
 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	int TT = 1;
//    cin >> TT;
	while (TT --) {
		solve ();
	}
	return 0;	                                    
}

Compilation message (stderr)

papricice.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main () {
      | ^~~~

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