oj.uz

Submission #1000059

# Submission time Handle Problem Language Result Execution time Memory
1000059 2024-06-16T14:26:03 Z BF001 Torrent (COI16_torrent) C++17
100 / 100
 326 ms 30140 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 300005

int dp[N], par[N], n, a, b;
vector<int> adj[N];

void init(int u, int p){
	for (auto x : adj[u]){
		if (x == p) continue;
		par[x] = u;
		init(x, u);
	}
}

bool cmp(int& a, int& b){
	return a > b;
}

int dfs(int u, int p, int x, int y){
	vector<int> tmp;
	dp[u] = 0;
	for (auto v : adj[u]){
		if (v == p) continue;
		if (u == x && v == y) continue;
		if (u == y && v == x) continue;
		dfs(v, u, x, y);
		tmp.push_back(dp[v] + 1);
	}
	sort(tmp.begin(), tmp.end(), cmp);
	for (int i = 0; i < (int) tmp.size(); i++){
		dp[u] = max(dp[u], tmp[i] + i);
	}
	return dp[u];
}

bool check(int x){
	int y = par[x];
	return dfs(a, 0, x, y) > dfs(b, 0, x, y);
}

int cal(int x){
	int y = par[x];
	return max(dfs(a, 0, x, y), dfs(b, 0, x, y));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> n >> a >> b;
    for (int i = 1; i <= n - 1; i++){
    	int u, v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    init(a, 0);

    int u = b;
    vector<int> path;
    while (u != a){
    	path.push_back(u);
    	u = par[u];
	}

	int l = 0, r = path.size() - 1, res = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(path[mid])){
			l = mid + 1;
			res = mid;
		}
		else r = mid - 1;
	}

	if (res < path.size() - 1) res++;
	int ans = cal(path[res]);
	if (res > 1) ans = min(ans, cal(path[res - 2]));
	if (res  + 2 <= path.size() - 1) ans = min(ans, cal(path[res + 2]));
	if (res > 0) ans = min(ans, cal(path[res - 1]));
	if (res < r) ans = min(ans, cal(path[res + 1]));
	
	cout << ans;

    return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:79:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  if (res < path.size() - 1) res++;
      |      ~~~~^~~~~~~~~~~~~~~~~
torrent.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  if (res  + 2 <= path.size() - 1) ans = min(ans, cal(path[res + 2]));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 26140 KB Output is correct
2 Correct 306 ms 27696 KB Output is correct
3 Correct 316 ms 29676 KB Output is correct
4 Correct 326 ms 28992 KB Output is correct
5 Correct 264 ms 25708 KB Output is correct
6 Correct 292 ms 26212 KB Output is correct
7 Correct 299 ms 30140 KB Output is correct