Submission #499626

#	Time	Username	Problem	Language	Result	Execution time	Memory
499626		saarang123	Torrent (COI16_torrent)	C++17	100 / 100	409 ms	27628 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
const int mxn = 300 * 1000 + 3;
vector<int> g[mxn];
int par[mxn];
int n, a, b;

void pars(int v = a, int p = -1) {
	for(int u : g[v]) if(u != p) {
		par[u] = v;
		pars(u, v);
	}
}

int dfs(int v, int p, int cut) {
	int ans = 0;
	vector<int> vals;
	for(int u : g[v]) if(u != p && u != cut) 
		vals.push_back(dfs(u, v, cut));
	sort(vals.begin(), vals.end(), greater<>());
	for(int i = 0; i < (int) vals.size(); i++)
		ans = max(ans, vals[i] + i + 1);
	return ans;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    cin >> n >> a >> b;
    for(int u, v, i = 1; i < n; i++) {
    	cin >> u >> v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    }
    pars();
    vector<int> path;
    int z = b;
    while(z)
    	path.push_back(z), z = par[z];
    reverse(path.begin(), path.end());
    // for(int o : path)
    // 	cout << o << ' ';
    // cout << endl;

    int mn = 0, mx = (int) path.size() - 2, last = 0;
    int ans = 2e9;
    while(mn <= mx) {
    	int mid = (mn + mx) >> 1;
    	int x = dfs(a, -1, path[mid]);
    	int y = dfs(b, -1, par[path[mid]]);
    	ans = min(ans, max(x, y));
    	//cout << mid << ' ' << x << ' ' << y << endl;
    	if(x <= y)
    		mn = mid + 1, last = mid;
    	else
    		mx = mid - 1;
    }
    if(last + 1 < path.size())
    	ans = min(ans, max(dfs(a, -1, path[last + 1]), dfs(b, -1, par[path[last + 1]])));
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(last + 1 < path.size())
      |        ~~~~~~~~~^~~~~~~~~~~~~

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