제출 #1167090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167090		InvMOD	Torrent (COI16_torrent)	C++20	100 / 100	282 ms	46040 KiB

torrent

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#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 x) -> int{
        blocked[u] = true;
        int answer = dp(x, -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;
    for(int i = lg - 1; i >= 0; i--){
        if(!par[i][node] || par[i][node] == a) continue;

        int nw_node = par[i][node];
        if(calc(par[0][nw_node], b) <= calc(nw_node, a)){
            node = nw_node;
        }
    }

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

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

컴파일 시 표준 에러 (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: 69 / 69