Submission #508705

#	Time	Username	Problem	Language	Result	Execution time	Memory
508705		Joo	Torrent (COI16_torrent)	C++17	0 / 100	120 ms	24420 KiB

torrent

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

const int N = 3e5+10;

int st[2], dp[N], tmp[N], n;
vector<int> G[N];

void dfs(int u, int p){
    for(int v : G[u]) if(v != p) dfs(v, u);
    
    vector<int> vec;
    for(int v : G[u]) if(v != p and v != st[1]) vec.emplace_back(dp[v]);

    sort(vec.rbegin(), vec.rend());
    for(int i = 0; i < vec.size(); i++){
        dp[u] = max(dp[u], vec[i]+i+1);
    }
}

 main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> st[0] >> st[1];
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(st[0], -1);
    int ans = max(dp[st[0]], dp[st[1]]);

    for(int i = 1; i <= n; i++) dp[i] = 0;
    swap(st[0], st[1]);
    dfs(st[0], -1);
    ans = min(ans, max(dp[st[0]], dp[st[1]]));

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(long long int, long long int)':
torrent.cpp:17:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
torrent.cpp: At global scope:
torrent.cpp:22:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 |  main(void){
      |  ^~~~

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