oj.uz

Submission #871273

# Submission time Handle Problem Language Result Execution time Memory
871273 2023-11-10T11:31:05 Z TahirAliyev Torrent (COI16_torrent) C++17
100 / 100
 448 ms 28832 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define oo 1e9

const int MAX = 3e5 + 5;
int n, a, b;

vector<int> g[MAX];
int par[MAX];
int sub[MAX];

void dfs(int node, int p){
    par[node] = p;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
    }
}

void dfs(int node, int p, int bar){
    vector<int> s;
    for(int to : g[node]){
        if(to == p || to == bar) continue;
        dfs(to, node, bar);
        s.push_back(sub[to]);
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < s.size(); i++){
        sub[node] = max(sub[node], s[i] + int(s.size()) - i);
    }
}

vector<int> v;

int main(){
    cin >> n >> a >> b;
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(a, a);
    v.push_back(b);
    while(v.back() != a){
        v.push_back(par[v.back()]);
    }
    int l = 0, r = v.size() - 2;
    int ans = oo;
    while(l <= r){
        memset(sub, 0, sizeof(sub));
        int mid = (l + r) / 2;
        dfs(a, a, v[mid]);
        dfs(b, b, v[mid + 1]);
        ans = min(ans, max(sub[a], sub[b]));
        if(sub[a] < sub[b]){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << ans << '\n';
}

Compilation message

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

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 22772 KB Output is correct
2 Correct 448 ms 27084 KB Output is correct
3 Correct 351 ms 28552 KB Output is correct
4 Correct 355 ms 27932 KB Output is correct
5 Correct 353 ms 25152 KB Output is correct
6 Correct 331 ms 25704 KB Output is correct
7 Correct 417 ms 28832 KB Output is correct