Submission #657746

#	Time	Username	Problem	Language	Result	Execution time	Memory
657746		Ronin13	Torrent (COI16_torrent)	C++14	0 / 100	264 ms	49300 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);
int x[NMAX][2];
ll dp[NMAX][2];
ll DP[NMAX][2];
vector <int> vec;
void calc(int v, int e, int ind){
    vector <ll> vv;
    int l = 0;
    for(int to : g[v]){
        if(to == e) continue;
        if(x[to][ind]){
            l = to;
            continue;
        }
        vv.pb(dp[to][ind]);
    }
    ll mx = 0;
    sort(vv.begin(), vv.end());
    reverse(vv.begin(), vv.end());
    for(int i = 0; i < vv.size(); i++){
        mx = max(mx, vv[i] + i + 1);
    }
    dp[v][ind] = mx;
    if(v == vec[ind]){
        DP[v][ind] = dp[v][ind];
        x[v][ind] = 1;
    }
    else{
        if(l == 0) return;
        DP[v][ind] = max(DP[l][ind] + 1, x[l][ind] + mx);
        x[v][ind] = x[l][ind] + 1;
    }
}

void dfs(int v, int ind,  int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, ind, v);
    }
    calc(v, e, ind);
}

vector <int> p(NMAX);
vector <int> path;
int a, b;
void DFS(int v, int e = -1){
    p[v] = e;
    if(v == b){
        while(v != -1){
            path.pb(v);
            v = p[v];
        }
        reverse(path.begin(), path.end());
        return;
    }
    for(int to : g[v]){
        if(to == e) continue;
        DFS(to, v);
    }
}

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);
    }
    for(int i= 1; i <= n; i++){
        dp[i][0] = dp[i][1] = DP[i][0] = DP[i][1] = 1e9;
    }
    vec.pb(b);
    vec.pb(a);
    dfs(a, 0);
    dfs(b, 1);
    DFS(a);
    /*for(int i= 1; i <= n; i++){
        cout << DP[i][1] << ' ' << DP[i][0] << "\n";
    }*/
    ll ans = 1e9;
    for(int i = 0; i < path.size() - 1; i++){
        int x = path[i], y = path[i + 1];
        ans = min(ans, max(DP[x][1], DP[y][0]));
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

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

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