oj.uz

Submission #870195

# Submission time Handle Problem Language Result Execution time Memory
870195 2023-11-07T08:30:01 Z Onur_Ilgaz Papričice (COCI20_papricice) C++17
0 / 110
 1000 ms 6492 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
vector <vector<int> > adj(N);
int under[N], n, mn = inf;
int val[3];
vector <int> lol;

void label(int node, int ata) {
	under[node] = 1;
	for(auto it:adj[node]) {
		if(it == ata) continue;
		label(it, node);
		under[node] += under[it];
		// cout << node << " " << it << " " << under[it] << "\n";
	}
}

void label(int node) {
	memset(under, 0, N * sizeof(int));
	label(node, 0);
}

int center(int node, int ata) {
	int to = 0;
	for(auto it:adj[node]) {
		if(it == ata) continue;
		if(under[it] >= (n + 1) / 2) {
			to = it;
			break;
		}
	}
	lol.push_back(1);
	if(!to) return node;
	return center(to, node);
}

int push(int node, int ata) {
	int mx = 0, mxnode = 0;
	for(auto it:adj[node]) {
		if(it == ata) continue;
		if(under[it] > mx) {
			mx = under[it];
			mxnode = it;
		}
	}
	return mxnode;
}

int32_t main(){
	fast
	cin>>n;
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	label(1);

	// for(int i = 1; i <= n; i++) {
	// 	cout << under[i] << " ";
	// } cout << "\n";

	int st = center(1, 0);

	// cout << st << "\n";

	label(st);

	// for(int i = 1; i <= n; i++) {
	// 	cout << under[i] << " ";
	// } cout << "\n";

	int a = st, b = 0;
	for(auto &it:adj[a]) {
		if(under[it] > under[b]) {
			b = it;
		}
	}
	val[0] = under[st] - under[b]; // a için
	val[1] = 0;
	val[2] = under[b]; // b için

	// cout << a << " " << b << "\n";

	int ata = b, atb = a;
	while(val[0] > val[1] or val[2] > val[1]) {
		// cout << val[0] << " " << val[1] << " " << val[2] << "\n";
		// cout << a << " " << b << "\n";

		if(val[0] > val[2]) {
			int prev = val[0];
			a = push(a, ata);
			val[1] += prev - under[a];
			val[0] = under[a];
			ata = a;
		}
		else {
			int prev = val[2];
			b = push(b, atb);
			val[1] += prev - under[b];
			val[2] = under[b];
			atb = b;
		}
		mn = min(mn, max(max(abs(val[0] - val[1]), abs(val[0] - val[2])), abs(val[1] - val[2])));
	}
	// cout << val[0] << " " << val[1] << " " << val[2] << "\n";
	// cout << a << " " << b << "\n";
	mn = min(mn, max(max(abs(val[0] - val[1]), abs(val[0] - val[2])), abs(val[1] - val[2])));
	cout << mn << "\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Execution timed out 1096 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Execution timed out 1096 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Execution timed out 1096 ms 6492 KB Time limit exceeded
3 Halted 0 ms 0 KB -