oj.uz

Submission #403577

# Submission time Handle Problem Language Result Execution time Memory
403577 2021-05-13T09:43:34 Z NurstanDuisengaliev Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 16476 KB 
// 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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Correct 4 ms 5024 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Correct 4 ms 5024 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 78 ms 5036 KB Output is correct
7 Correct 78 ms 5152 KB Output is correct
8 Correct 80 ms 5120 KB Output is correct
9 Correct 68 ms 5128 KB Output is correct
10 Correct 85 ms 5124 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Correct 4 ms 5024 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 78 ms 5036 KB Output is correct
7 Correct 78 ms 5152 KB Output is correct
8 Correct 80 ms 5120 KB Output is correct
9 Correct 68 ms 5128 KB Output is correct
10 Correct 85 ms 5124 KB Output is correct
11 Execution timed out 1087 ms 16476 KB Time limit exceeded
12 Halted 0 ms 0 KB -