oj.uz

Submission #859054

# Submission time Handle Problem Language Result Execution time Memory
859054 2023-10-09T15:21:47 Z LeonaRaging Torrent (COI16_torrent) C++14
100 / 100
 344 ms 29884 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 3e5 + 4;

struct Edge {
	int u, v; bool used, bad;
	int get(int x) {
		return u ^ v ^ x;
	}
	Edge(int u = 0, int v = 0): 
		u(u), v(v) {
			used = bad = 0;
		}
};

int n, a, b, res, par[maxn], dp[maxn];
vector<int> adj[maxn];
vector<Edge> edges;
vector<int> myVec;

void dfs(int u, int p) {
	for (int i : adj[u]) {
		int v = edges[i].get(u);
		if (v != p)
			par[v] = i,
			dfs(v, u);
	}
}

void dfs(int u) {
	dp[u] = 0;
	vector<int> cur;
	for (int i : adj[u]) if (!edges[i].used && !edges[i].bad) {
		edges[i].used = 1;
		int v = edges[i].get(u);
		dfs(v);
		cur.pb(v);
	}
	sort(all(cur), [&](int u, int v) {
		return dp[u] > dp[v];
	});
	for (int i = 0; i < SZ(cur); i++)
		dp[u] = max(dp[u], dp[cur[i]] + i + 1);
}

bool ok(int m) {
	for (int i = 0; i < n - 1; i++)
		edges[i].used = 0;
	edges[myVec[m]].bad = 1;	
	dfs(a); dfs(b);
	edges[myVec[m]].bad = 0;
	res = min(res, max(dp[a], dp[b]));	
	return (dp[a] > dp[b]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1, u, v; i < n; i++) {
    	cin >> u >> v;
    	adj[u].pb(i - 1);
    	adj[v].pb(i - 1);
    	edges.pb(u, v);
    }
    dfs(a, 0);
    int u = b;
    while (u != a) {
    	myVec.pb(par[u]);
    	u = edges[par[u]].get(u);
    }
    int L = 0, R = SZ(myVec) - 1;
    res = n;
    while (L <= R) {
    	int m = (L + R) / 2;
    	if (ok(m)) L = m + 1;
    	else R = m - 1;
    }
    cout << res;
}

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 26740 KB Output is correct
2 Correct 344 ms 27116 KB Output is correct
3 Correct 334 ms 29604 KB Output is correct
4 Correct 319 ms 28408 KB Output is correct
5 Correct 299 ms 26092 KB Output is correct
6 Correct 271 ms 26616 KB Output is correct
7 Correct 277 ms 29884 KB Output is correct