oj.uz

답안 #859051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859051 2023-10-09T15:09:05 Z LeonaRaging Torrent (COI16_torrent) C++14
69 / 100
 116 ms 28916 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, 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) {
	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);
}

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 = 1e9;
    while (L <= R) {
    	int m = (L + R) / 2;
    	for (int i = 0; i < SZ(myVec); 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]));
    	if (dp[a] < dp[b]) L = m + 1;
    	else R = m - 1;
    }
    cout << res;
}

Subtask #1
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 26872 KB Output is correct
2 Correct 95 ms 27088 KB Output is correct
3 Correct 116 ms 28916 KB Output is correct
4 Correct 87 ms 27384 KB Output is correct
5 Correct 90 ms 25444 KB Output is correct
6 Correct 88 ms 25596 KB Output is correct
7 Correct 106 ms 26872 KB Output is correct