Submission #374736

#	Time	Username	Problem	Language	Result	Execution time	Memory
374736		ntabc05101	Torrent (COI16_torrent)	C++14	100 / 100	559 ms	30264 KiB

torrent

#include<bits/stdc++.h>

const int max_n=300000;

int n, a, b;
int dp[5+max_n];
int parent[5+max_n];
std::vector<int> adjList[5+max_n];

void dfs(int vertex) {
	for (auto& to: adjList[vertex]) {
		if (to!=parent[vertex]) {
			parent[to]=vertex;
			dfs(to);
		}
	}
}

int solve(int vertex, int parent, int cx, int cy) {
	dp[vertex]=0;
	std::vector<int> c;
	for (auto& to: adjList[vertex]) {
		if (to==parent) continue;
		if (vertex==cx and to==cy) continue;
		if (vertex==cy and to==cx) continue;

		c.push_back(solve(to, vertex, cx, cy));
	}

	std::sort(c.rbegin(), c.rend());
	for (int i=0; i<c.size(); ++i) {
		dp[vertex]=std::max(dp[vertex], c[i]+i+1);
	}

	return dp[vertex];
}

int delta(int vertex) {
	return solve(a, 0, vertex, parent[vertex])
				-solve(b, 0, vertex, parent[vertex]);
}
int calc(int vertex) {
	return std::max(solve(a, 0, vertex, parent[vertex]), 
				solve(b, 0, vertex, parent[vertex]));
}

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);

	std::cin>>n>>a>>b;
	for (int i=1; i<n; ++i) {
		int v1, v2; std::cin>>v1>>v2;
		adjList[v1].push_back(v2);
		adjList[v2].push_back(v1);
	}

	dfs(a);
	std::vector<int> par;
	for (int i=b; i!=a; i=parent[i]) {
		par.push_back(i);
	}

	int low=0, high=par.size();
	while (low<high) {
		int mid=low+high>>1;

		if (delta(par[mid])>0) {
			low=mid+1;
		}
		else {
			high=mid;
		}
	}

	int result=calc(par[low]);
	if (low) result=std::min(result, calc(par[low-1]));
	if (low+1<par.size()) result=std::min(result, calc(par[low+1]));

	std::cout<<result<<"\n";
}

Compilation message (stderr)

torrent.cpp: In function 'int solve(int, int, int, int)':
torrent.cpp:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i=0; i<c.size(); ++i) {
      |                ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=low+high>>1;
      |           ~~~^~~~~
torrent.cpp:77:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  if (low+1<par.size()) result=std::min(result, calc(par[low+1]));
      |      ~~~~~^~~~~~~~~~~

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