제출 #990734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990734		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	293 ms	26360 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;

    block = path[1];
    dfs(a);
    block = path[0];
    dfs(b);
    ans = min(ans, max(dp[a], dp[b]));

    if (dp[a] > dp[b]){
        cout << ans << endl;
        return 0;
    }

    int l = 1;
    int r = path.size();

    while (r - l > 1){
        int mid = (l + r) / 2;

        block = path[mid];
        dfs(a);
        block = path[mid - 1];
        dfs(b);

        if (dp[a] <= dp[b])
            l = mid;
        else
            r = mid;

        ans = min(ans, max(dp[a], dp[b]));
    }

    l++;
    if (l < path.size()){
        block = path[l];
        dfs(a);
        block = path[l - 1];
        dfs(b);
        ans = min(ans, max(dp[a], dp[b]));
    }

    cout << ans << endl;
}

컴파일 시 표준 에러 (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:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (l < path.size()){
      |         ~~^~~~~~~~~~~~~

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