Submission #383474

#	Time	Username	Problem	Language	Result	Execution time	Memory
383474		pure_mem	Torrent (COI16_torrent)	C++14	31 / 100	145 ms	27712 KiB

torrent

#include <iostream>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 3e5 + 12;
const int INF = 1e9;

int n, root1, timer, parent[N], tin[N], tout[N], root2, dp[N];
vector< int > g[N];

void dfs(int v, int pr){
	tin[v] = ++timer, parent[v] = pr;
	for(int to: g[v])
		if(to != pr)
			dfs(to, v);
	tout[v] = ++timer;
}
void dfs1(int v, int pr){
	vector< int > tmp;
	for(int to: g[v]){
		if(to != pr){
			dfs1(to, v);
			if(!(tin[to] <= tin[root2] && tout[root2] <= tout[to])){
				tmp.push_back(dp[to]);
			}
		}
	}
	sort(tmp.begin(), tmp.end(), 
		[](int x, int y){
			return x > y;
		}
	);
	for(int i = 0;i < (int)tmp.size();i++)
		dp[v] = max(dp[v], i + 1 + tmp[i]);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> root1 >> root2;
	for(int i = 1, x, y;i < n;i++){
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(root1, -1);
	dfs1(root1, -1);
	vector< int > ord, pref, suf;
	int cur = root2;
	while(cur != -1){
		ord.push_back(cur), pref.push_back(dp[cur]), suf.push_back(dp[cur]);
	//	cerr << cur << " " << dp[cur] << "\n";
		cur = parent[cur];
	}
	pref[0] = pref[0] + 1;
	for(int i = 1;i < (int)pref.size();i++)
		pref[i] = max(pref[i] + i + 1, pref[i - 1]);
	suf[(int)suf.size() - 1] = suf.back() + 1;
	for(int i = (int)suf.size() - 2, j = 1;i >= 0;i--, j++)
		suf[i] = max(suf[i] + j + 1, suf[i + 1]);
	int ans = INF;
	if(ord.size() == 1)
		ans = dp[root1];
	for(int i = 0;i + 1 < (int)ord.size();i++){
		int p1 = dp[ord[i]] + i, p2 = dp[ord[i + 1]] + (int)ord.size() - i - 2;
		if(i > 0)
			p1 = max(p1, pref[i - 1]);
		if(i + 2 < (int)ord.size())
			p2 = max(p2, suf[i + 2]);
		ans = min(ans, max(p1, p2));
	}
	cout << ans;
}

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