제출 #990729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990729		vjudge1	Torrent (COI16_torrent)	C++17	0 / 100	2083 ms	22096 KiB

torrent

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

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

void get_path(int a, int b){
    path.push_back(a);
    vis[a] = 1;

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

    for (int u : g[a]){
        if (vis[u]) continue;
        get_path(u, b);

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

    path.pop_back();
}

int block;
void dfs(int v, int p = -1){
    // cout << "I am at " << v << endl;
    vis[v] = 1;
    bool leaf = 1;
    for (int u : g[v]){
        if (vis[u]) 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();
        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 ++){
        memset(vis, 0, sizeof vis);
        vis[path[i]] = 1;
        // cout << "Marked " << path[i] << " as visited" << endl;
        // cout << "Calling dfs on " << a << endl;
        block = path[i];
        dfs(a);
        vis[path[i]] = 0;
        // cout << "Marked " << path[i] << " as unvisited" << endl;
        // cout << "Calling dfs on " << b << endl;
        block = path[i - 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:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < vec.size(); i ++){
      |                         ~~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 1; i < path.size(); i ++){
      |                     ~~^~~~~~~~~~~~~

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