Submission #759635

#	Time	Username	Problem	Language	Result	Execution time	Memory
759635		nonono	Torrent (COI16_torrent)	C++14	100 / 100	355 ms	28248 KiB

torrent

#include "bits/stdc++.h"
#define SZ(x) (int)(x.size())
using namespace std;

void file(string name = ""){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    if(name != ""){
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

const int mxN = 3e5 + 10;
int n, a, b;
vector<vector<int>> adj(mxN);

bool Check;
vector<int> path;
int dp[mxN];

void findAB(int u, int p){
    path.push_back(u);

    if(u == b){
        Check = true;
        return ;
    }

    for(int v : adj[u]){
        if(v == p) continue ;
        findAB(v, u);
        if(Check) return ;
    }

    path.pop_back();
}

void dfs(int u, int par1, int par2){
    dp[u] = 0;

    vector<int> child;
    for(int v : adj[u]){
        if(v == par1 || v == par2) continue ;
        dfs(v, u, par2);

        child.push_back(dp[v]);
    }

    sort(child.begin(), child.end());
    reverse(child.begin(), child.end());

    for(int i = 0; i < child.size(); i ++){
        dp[u] = max(dp[u], child[i] + i + 1);
    }
}

bool check(int i){
    int x = path[i];
    int y = path[i + 1];
    
    dfs(a, -1, y);
    dfs(b, -1, x);
    
    return dp[a] < dp[b];
}

int main(){
    file("");

    cin.tie(0)->sync_with_stdio(0);

    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);
    }

    Check = false;
    findAB(a, -1);
    
    int low = 0, high = SZ(path) - 2;
    while(low <= high){
        int mid = (low + high) / 2;
        if(check(mid)){
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    check(low);
    int res = max(dp[a], dp[b]);
    
    if(low - 1 >= 0){
        low -- ;
        check(low);
        res = min(res, max(dp[a], dp[b]));
    }
    
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < child.size(); i ++){
      |                    ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'void file(std::string)':
torrent.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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