Submission #844863

#	Time	Username	Problem	Language	Result	Execution time	Memory
844863		Cookie	Torrent (COI16_torrent)	C++14	100 / 100	381 ms	35480 KiB

torrent

#include<bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(v) (int)v.size()
using namespace std;
const ll base = 107, mod = 1e9 + 7;
const int mxn = 3e5 + 5, inf = 1e9, sq = 400;
int a, b, n;
vt<pii>adj[mxn + 1];
int pa[mxn + 1], toedge[mxn + 1];
int tin[mxn + 1], tout[mxn + 1], colour[mxn + 1], tt = 0;
int dp[mxn + 1];
bool vis = 0;
bool inside(int u, int v){
    return(tin[u] <= tin[v] && tout[v] <= tout[u]);
}
void dfs(int s, int pre){
    tin[s] = ++tt; 
    pa[s] = pre;
    for(auto [i, id]: adj[s]){
        if(i != pre){
            toedge[i] = id;
            dfs(i, s);
        }
    }
    tout[s] = tt;
}
int dfs_dp(int s, int pre, int co){
    dp[s] = 0;
    vt<int>comp;
    for(auto [i, id]: adj[s]){
        if(i != pre && colour[id] == co){
            comp.pb(dfs_dp(i, s, co));
        }
    }
    sort(comp.rbegin(), comp.rend());
    for(int i = 0; i < sz(comp); i++){
        dp[s] = max(dp[s], comp[i] + i + 1);
    }
    return(dp[s]);
}
vt<int>comp;
int f(int mid, bool search){
    int root = comp[mid];
        //cout << root << " ";
        for(int j = 1; j <= n; j++){
            if(j != root && inside(root, j)){
                
                colour[toedge[j]] = 2;
            }else{
                colour[toedge[j]] = 1;
            }
        }
        colour[toedge[root]] = 3;
        
        int cand1 = dfs_dp(a, -1, 1), cand2 = dfs_dp(b, -1, 2);
        //for(int j = 1; j <= n; j++)cout << dp[j] << " ";
        if(search)return(cand1 >= cand2);
        return(max(cand1, cand2));
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb({v, i}); adj[v].pb({u, i});
    }
    dfs(a, -1);
    
    int ver = b;
    while(ver != a){
        comp.pb(ver); ver = pa[ver];
    }
    int res = inf;
    int l = 0, r = sz(comp) - 1, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(f(mid, 1)){
            ans = mid; l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    if(ans != -1)res = min(res, f(ans, 0));
    if(ans != sz(comp) - 1)res = min(res, f(ans + 1, 0));
    cout << res;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [i, id]: adj[s]){
      |              ^
torrent.cpp: In function 'int dfs_dp(int, int, int)':
torrent.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto [i, id]: adj[s]){
      |              ^

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