Submission #871272

#	Time	Username	Problem	Language	Result	Execution time	Memory
871272		TahirAliyev	Torrent (COI16_torrent)	C++17	31 / 100	111 ms	29028 KiB

torrent

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define oo 1e9

const int MAX = 2e5 + 5;
int n, a, b;

vector<int> g[MAX];
int par[MAX];
int sub[MAX];

void dfs(int node, int p){
    par[node] = p;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
    }
}

void dfs(int node, int p, int bar){
    vector<int> s;
    for(int to : g[node]){
        if(to == p || to == bar) continue;
        dfs(to, node, bar);
        s.push_back(sub[to]);
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < s.size(); i++){
        sub[node] = max(sub[node], s[i] + int(s.size()) - i);
    }
}

vector<int> v;

int main(){
    cin >> n >> a >> b;
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(a, a);
    v.push_back(b);
    while(v.back() != a){
        v.push_back(par[v.back()]);
    }
    int l = 0, r = v.size() - 2;
    int ans = oo;
    while(l <= r){
        memset(sub, 0, sizeof(sub));
        int mid = (l + r) / 2;
        dfs(a, a, v[mid]);
        dfs(b, b, v[mid + 1]);
        ans = min(ans, max(sub[a], sub[b]));
        if(sub[a] < sub[b]){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << ans << '\n';
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~

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