oj.uz

Submission #657763

# Submission time Handle Problem Language Result Execution time Memory
657763 2022-11-11T01:10:45 Z Ronin13 Torrent (COI16_torrent) C++14
100 / 100
 573 ms 29676 KB 
#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 = 3e5 + 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;
pii 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 {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() - 1;
    /*for(int to : path){
        cout << to << ' ';
    }*/
    while(l + 1 < r){
        int mid = (l + r) / 2;
        pii val = compute(mid);
        if(val.f > val.s) r = mid;
        else l = mid;
    }
    int x = compute(r).f;
    if(r  > 0) x = min(x, compute(r - 1).s);
    cout << x;
    return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 22644 KB Output is correct
2 Correct 524 ms 28172 KB Output is correct
3 Correct 573 ms 29360 KB Output is correct
4 Correct 488 ms 28764 KB Output is correct
5 Correct 515 ms 26156 KB Output is correct
6 Correct 518 ms 26688 KB Output is correct
7 Correct 460 ms 29676 KB Output is correct