oj.uz

Submission #446928

# Submission time Handle Problem Language Result Execution time Memory
446928 2021-07-23T22:48:40 Z SirCovidThe19th Torrent (COI16_torrent) C++14
100 / 100
 612 ms 26520 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mx = 3e5+5;

int n, a, b; vector<int> adj[mx], pth; bool stop = 0;

void getPath(int i, int p){
    if (!stop) pth.push_back(i);
    if (i == b) stop = 1;
    for (int nxt : adj[i]) if (nxt != p) getPath(nxt, i);
    if (!stop) pth.pop_back();
}int calc(int i, int p, int no){
    vector<int> vals; int ret = 0;
    for (int nxt : adj[i]) if (nxt != p and nxt != no) vals.push_back(calc(nxt, i, no));
    sort(vals.begin(), vals.end(), greater<int>());
    for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
    return ret;
}void solve(){
    int low = 0, high = pth.size()-2, res = 1e9;
    while (low <= high){
        int mid = (low+high)/2; int x = calc(a, 0, pth[mid+1]), y = calc(b, 0, pth[mid]);
        res = min(res, max(x, y));
        (x < y) ? (low = mid+1) : (high = mid-1);
    }cout<<res<<endl;
}

int main(){
    cin >> n >> a >> b;
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }getPath(a, 0); solve();
}

Compilation message

torrent.cpp: In function 'int calc(int, int, int)':
torrent.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
      |                     ~~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 23224 KB Output is correct
2 Correct 573 ms 24500 KB Output is correct
3 Correct 571 ms 26052 KB Output is correct
4 Correct 588 ms 25684 KB Output is correct
5 Correct 553 ms 22580 KB Output is correct
6 Correct 521 ms 23336 KB Output is correct
7 Correct 514 ms 26520 KB Output is correct