Submission #501289

#	Time	Username	Problem	Language	Result	Execution time	Memory
501289		aryan12	Torrent (COI16_torrent)	C++17	0 / 100	146 ms	34024 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 5;
vector<int> g[N];
int minNum[N];
int tin[N], tout[N], tim = 0;
int n, a, b;
vector<pair<int, int> > values(N); //for nodes between A->B
int max1 = 0, max2 = 0, max3 = 0;

void dfsTime(int node, int par) {
	tin[node] = ++tim;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] != par) {
			dfsTime(g[node][i], node);
		}
	}
	tout[node] = ++tim;
}

void dfs(int node, int par) {
	//cout << "node = " << node << "\n";
	minNum[node] = 0; //min turns to colour the subtree of this node 
	vector<int> childDp;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par) {
			continue;
		}
		//cout << "node = " << node <<", g[node][i] = " << g[node][i] << "\n";
		dfs(g[node][i], node);
		childDp.push_back(minNum[g[node][i]]);
	}
	if(childDp.size() == 0) {
		return;
	}
	sort(childDp.begin(), childDp.end());
	int ans = 0, cnt = 0;
	for(int i = childDp.size() - 1; i >= 0; i--) {
		ans = max(ans, childDp[i] + ++cnt);
	}
	minNum[node] = ans;
}

void DfsB(int node, int par) {
	//cout << "DfsB -- node = " << node << ", par = " << par << "\n";
	values[node].second = 0;
	vector<int> children;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par || g[node][i] == a) {
			continue;
		}
		if(node == b && tin[g[node][i]] > tin[node]) {
			continue;
		}
		DfsB(g[node][i], node);
		children.push_back(values[g[node][i]].second);
	}
	sort(children.begin(), children.end());
	reverse(children.begin(), children.end());
	int ans = 0;
	for(int i = 0; i < children.size(); i++) {
		ans = max(ans, children[i] + i + 1);
	}
	values[node].second = ans;
	max2 = max(max2, ans);
}

void DfsA(int node, int par) {
	//cout << "DfsA -- node = " << node << ", par = " << par << "\n";
	values[node].first = 0;
	vector<int> children;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par || g[node][i] == b || tin[g[node][i]] > tout[b]) {
			continue;
		}
		DfsA(g[node][i], node);
		children.push_back(values[g[node][i]].first);
	}
	sort(children.begin(), children.end());
	reverse(children.begin(), children.end());
	int ans = 0;
	for(int i = 0; i < children.size(); i++) {
		ans = max(ans, children[i] + i + 1);
	}
	values[node].first = ans;
	max1 = max(max1, ans);
}

void Solve() {
	cin >> n >> a >> b;
	//cout << "a = " << a << ", b = " << b << "\n";
	bool f1 = false;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		if((u == a && v == b) || (u == b || v == a)) {
			f1 = true;
		}
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfsTime(a, -1);
	dfs(a, -1); //only calculate from A to other nodes

	int minans = 0; //all other subtrees from A except the one which contains B
	vector<int> childVal;
	for(int i = 0; i < g[a].size(); i++) {
		if(tin[g[a][i]] <= tin[b] && tout[g[a][i]] >= tout[b]) {
			continue;
		}
		childVal.push_back(minNum[g[a][i]]);
	}
	sort(childVal.begin(), childVal.end());
	reverse(childVal.begin(), childVal.end());
	for(int i = 0; i < childVal.size(); i++) {
		minans = max(minans, childVal[i] + i + 1);
	}
	int minansforB = minNum[b];
	//cout << "minans = " << minans << ", minansforB = " << minansforB << "\n";
	/*for(int i = 1; i <= n; i++) {
		cout << "i = " << i << ", minNum[i] = " << minNum[i] << "\n";
	}
	cout << "\n";*/
	//only thing left - cover the gap between a and b -- might be a whole subtree!
	DfsB(b, -1);
	DfsA(a, -1);
	for(int i = 1; i <= n; i++) {
		if(values[i].first != 0 || values[i].second != 0) {
			max3 = max(max3, min(values[i].first, values[i].second));
		}
	}
	//max3 = min(max1, max2);

	int finalans = INT_MAX;
	if(f1) finalans = min(finalans, max({minans, minansforB}));
	finalans = min(finalans, max({minans + 1, minansforB, max1}));
	finalans = min(finalans, max({minans, minansforB + 1, max2}));
	finalans = min(finalans, max({minans + 1, minansforB + 1, max3}));
	cout << finalans << "\n";
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfsTime(long long int, long long int)':
torrent.cpp:17:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void dfs(long long int, long long int)':
torrent.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void DfsB(long long int, long long int)':
torrent.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
torrent.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < children.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'void DfsA(long long int, long long int)':
torrent.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
torrent.cpp:86:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 0; i < children.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'void Solve()':
torrent.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0; i < g[a].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
torrent.cpp:119:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i = 0; i < childVal.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69