Submission #1167068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167068		InvMOD	Torrent (COI16_torrent)	C++20	31 / 100	354 ms	47816 KiB

torrent

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

template<typename T> bool ckmn(T& a, const T& b){
    if(a >= b)
        return a = b, true;
    return false;
}

const int lg = 20;

void solve()
{
    int n,a,b; cin >> n >> a >> b;

    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 2; i <= n; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<int>> par(lg, vector<int>(n + 1));
    function<void(int,int)> preDFS = [&](int x, int p) -> void{
        for(int v : adj[x])if(v != p){
            par[0][v] = x;
            for(int i = 1; i < lg; i++)
                par[i][v] = par[i - 1][par[i - 1][v]];
            preDFS(v, x);
        }
    };
    preDFS(a, -1);

    vector<bool> blocked(n + 1, false);
    function<int(int,int)> dp = [&](int x, int p) -> int{

        vector<int> save_dp;
        for(int v : adj[x])if(v != p){
            if(blocked[v]) continue;
            save_dp.push_back(dp(v, x) + 1);
        }

        sort(all(save_dp), greater<int>());

        int answer = 0;
        for(int i = 0; i < sz(save_dp); i++){
            answer = max(answer, save_dp[i] + i);
        }
        return answer;
    };

    auto calc = [&](int u) -> int{
        blocked[par[0][u]] = true;
        int answer = dp(b, -1);
        blocked[par[0][u]] = false;

        blocked[u] = true;
        answer = max(answer, dp(a, -1));
        blocked[u] = false;

        return answer;
    };

    // a is the root
    // nearer the block node to a is, the more b will need, the least a will need
    // -> binary search to find the optimal node

    int node = b, answer = calc(b);
    for(int i = lg - 1; i >= 0; i--){
        if(!par[i][node]) continue;

        if(ckmn(answer, calc(par[i][node]))){
            node = par[i][node];
        }
    }

    if(node != a){
        ckmn(answer, calc(par[0][node]));
    }

    cout << answer << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int32_t main()':
torrent.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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