oj.uz

Submission #499626

# Submission time Handle Problem Language Result Execution time Memory
499626 2021-12-29T05:46:34 Z saarang123 Torrent (COI16_torrent) C++17
100 / 100
 409 ms 27628 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 5 ms 7348 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 20380 KB Output is correct
2 Correct 399 ms 21668 KB Output is correct
3 Correct 353 ms 23152 KB Output is correct
4 Correct 370 ms 26788 KB Output is correct
5 Correct 373 ms 23884 KB Output is correct
6 Correct 409 ms 24596 KB Output is correct
7 Correct 338 ms 27628 KB Output is correct