Submission #657710

#	Time	Username	Problem	Language	Result	Execution time	Memory
657710		Ronin13	Torrent (COI16_torrent)	C++14	0 / 100	245 ms	47880 KiB

torrent

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define epb emplace_back
#define pb push_back
#define ull unsigned ll
using namespace std;

const int NMAX =  1e6 + 1;
vector <vector <int> > g(NMAX);
vector <bool> x(NMAX);
vector <int> dp(NMAX, 1e9), DP(NMAX, 1e9);

int a, b;

void dfs(int v, int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    vector <int> vv;
    for(int to : g[v]){
        if(to == e) continue;
        vv.pb(dp[to]);
    }
    sort(vv.begin(), vv.end());
    reverse(vv.begin(), vv.end());
    int mx = 0;
    for(int i = 0; i < vv.size(); i++){
        mx = max(mx, vv[i] + i + 1);
    }
    dp[v] = mx;
    vv.clear();
    int l = 0;
    for(int to : g[v]){
        if(to == e) continue;
        if(x[to]) {
            l = to;
            continue;
        }
        vv.pb(dp[to]);
    }
    sort(vv.begin(), vv.end());
    reverse(vv.begin(), vv.end());
    mx = 0;
    for(int i = 0; i < vv.size(); i++){
        mx = max(mx, vv[i] + i + 1);
    }
    dp[v] = min(dp[v], max(mx, DP[l]));
    DP[v] = min(DP[v], mx + DP[l] + 1);
    if(v == b) DP[v] = dp[v], x[v] = true;
    if(l) x[v] = true;
}

int main(){
    int n; cin >> n;
    cin >> a >> b;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs(a);
    /*for(int i = 1; i <= n; i++){
        cout << dp[i] << ' ' << DP[i] << "\n";
    }*/
    cout << min(dp[a], DP[a]);
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < vv.size(); i++){
      |                    ~~^~~~~~~~~~~
torrent.cpp:49:22: 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 < vv.size(); i++){
      |                    ~~^~~~~~~~~~~

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