oj.uz

Submission #509107

# Submission time Handle Problem Language Result Execution time Memory
509107 2022-01-14T02:57:15 Z Joo Torrent (COI16_torrent) C++17
100 / 100
 387 ms 23752 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5+10, INF = 1e9+10;

int st[2], dp[N], tmp[N], n;
vector<int> G[N], lis;

bool pre(int u, int p){
    if(u == st[1]){
        lis.emplace_back(u);
        return true;
    }
    for(int v : G[u]){
        if(v == p) continue;
        if(pre(v, u)){
            lis.emplace_back(u);
            return true;
        } 
    }
    return false;
}

void dfs(int u, int p, int ban){
    for(int v : G[u]) if(v != p and v != ban) dfs(v, u, ban);
    
    vector<int> vec;
    for(int v : G[u]) if(v != p and v != ban) vec.emplace_back(dp[v]);

    sort(vec.rbegin(), vec.rend());
    for(int i = 0; i < vec.size(); i++){
        dp[u] = max(dp[u], vec[i]+i+1);
    }
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> st[0] >> st[1];
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    pre(st[0], -1);

    int l = 0, r = (int)lis.size()-2, ans = INF;
    while(l <= r){
        int mid = (l+r)>>1;

        for(int i = 0; i <= n; i++) dp[i] = 0;
        // assert(mid+1 <= (int)lis.size()-1);
        dfs(st[1], -1, lis[mid+1]);
        dfs(st[0], -1, lis[mid]);

        ans = min(ans, max(dp[st[0]], dp[st[1]]));

        if(dp[st[0]] < dp[st[1]]){
            r = mid-1;
        } else {
            l = mid+1;
        }
    }

    cout << ans << "\n";

    return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:31:22: 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 < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 4 ms 7368 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 20512 KB Output is correct
2 Correct 387 ms 22220 KB Output is correct
3 Correct 356 ms 23384 KB Output is correct
4 Correct 331 ms 22864 KB Output is correct
5 Correct 333 ms 20068 KB Output is correct
6 Correct 314 ms 20616 KB Output is correct
7 Correct 310 ms 23752 KB Output is correct