Submission #657760

#	Time	Username	Problem	Language	Result	Execution time	Memory
657760		Ronin13	Torrent (COI16_torrent)	C++14	0 / 100	133 ms	24812 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 = 2e5 + 1;
vector <vector <int> > g(NMAX);
vector <int> path;
int dp[NMAX][2];

void dfs(int v, int ind, int e = -1){
    for(int to : g[v]){
        if(to && to != e){
            dfs(to, ind, v);
        }
    }
    vector <int> vv;
    for(int to : g[v]){
        if(to && to != e){
            vv.pb(dp[to][ind]);
        }
    }
    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][ind] = mx;
}
int a, b;
int compute(int x){
    int v = path[x];
    int u = path[x + 1];
    for(int &to : g[v]){
        if(to == u) to = 0;
    }
    for(int &to : g[u]){
        if(to == v) to = 0;
    }
    dfs(a, 0);
    dfs(b, 1);
    for(int &to : g[v]){
        if(!to) to = u;
    }
    for(int &to : g[u]){
        if(!to) to = v;
    }
    return max(dp[a][0], dp[b][1]);
}

vector <int> p(NMAX);
void DFS(int v, int e = -1){
    p[v] = e;
    if(v == b){
        while(v > 0){
            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);
    }
    DFS(a);
    int l = -1, r = path.size() - 2;
    /*for(int to : path){
        cout << to << ' ';
    }*/
    while(l + 1 < r){
        int mid = (l + r) / 2;
        int val = compute(mid);
        int val1 = compute(mid + 1);
        if(val > val1) l = mid;
        else r = mid;
    }
    int x = compute(r);
    cout << x;
    return 0;
}

Compilation message (stderr)

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

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