oj.uz

Submission #383482

# Submission time Handle Problem Language Result Execution time Memory
383482 2021-03-30T04:29:56 Z pure_mem Torrent (COI16_torrent) C++14
100 / 100
 150 ms 39376 KB 
#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 = 6e5 + 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];
	}
	for(int i = 1;i < (int)pref.size();i++)
		pref[i] = max(pref[i] + i, pref[i - 1]);
	for(int i = (int)suf.size() - 2, j = 1;i >= 0;i--, j++)
		suf[i] = max(suf[i] + j, 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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 11 ms 14572 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 31040 KB Output is correct
2 Correct 147 ms 36460 KB Output is correct
3 Correct 140 ms 38980 KB Output is correct
4 Correct 150 ms 37656 KB Output is correct
5 Correct 149 ms 34616 KB Output is correct
6 Correct 130 ms 35192 KB Output is correct
7 Correct 128 ms 39376 KB Output is correct