Submission #990733

#	Time	Username	Problem	Language	Result	Execution time	Memory
990733		vjudge1	Torrent (COI16_torrent)	C++17	31 / 100	2045 ms	21840 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;
int n, a, b, dp[N];
vector<int> g[N], path;

void get_path(int a, int b){
    path.push_back(a);
    if (path.back() == b) return;

    for (int u : g[a]){
        if (path.size() >= 2 and path[path.size() - 2] == u)
            continue;

        if (path.back() == b) return;
        get_path(u, b);
        if (path.back() == b) return;
    }

    if (path.back() == b) return;
    path.pop_back();
}

int block;
void dfs(int v, int p = -1){
    // cout << "I am at " << v << endl;
    bool leaf = 1;
    for (int u : g[v]){
        if (u == p or u == block) continue;
        leaf = 0;
        dfs(u, v);
    }

    if (leaf){
        dp[v] = 0;
    }
    else{
        vector<int> vec;
        for (int u : g[v]){
            if (u == block or u == p) continue;
            vec.push_back(dp[u]);
        }
        sort(vec.begin(), vec.end());

        int tme = vec.size();
        dp[v] = 0;
        for (int i = 0; i < vec.size(); i ++){
            dp[v] = max(dp[v], vec[i] + tme);
            tme--;
        }
    }

    // cout << "computed dp[" << v << "] = " << dp[v] << endl;
}

int main(){
    cin >> n >> a >> b;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    get_path(a, b);
    int ans = n + 10;

    // for (int v : path)
    //     cout << v << " ";
    // cout << endl;

    for (int i = 1; i < path.size(); i ++){
        // cout << "Calling dfs on " << a << endl;
        block = path[i];
        dfs(a);
        // cout << "Calling dfs on " << b << endl;
        block = path[i - 1];
        dfs(b);
        ans = min(ans, max(dp[a], dp[b]));
    }

    cout << ans << endl;
}

Compilation message (stderr)

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

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