oj.uz

Submission #844863

# Submission time Handle Problem Language Result Execution time Memory
844863 2023-09-06T06:06:01 Z Cookie Torrent (COI16_torrent) C++14
100 / 100
 381 ms 35480 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 3 ms 12376 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 29008 KB Output is correct
2 Correct 353 ms 33580 KB Output is correct
3 Correct 325 ms 35040 KB Output is correct
4 Correct 339 ms 34744 KB Output is correct
5 Correct 331 ms 31312 KB Output is correct
6 Correct 302 ms 31992 KB Output is correct
7 Correct 309 ms 35480 KB Output is correct