oj.uz

Submission #719873

# Submission time Handle Problem Language Result Execution time Memory
719873 2023-04-06T23:59:19 Z Ahmed57 Torrent (COI16_torrent) C++14
100 / 100
 820 ms 26388 KB 
#include <bits/stdc++.h>

using namespace std;
int par[300001];
vector<int> adj[300001];
void dfs(int i,int pr){
    par[i]= pr;
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
    }
}
int vis[300001];
long long calc(int i,int pr){
    if(vis[i]==1)return 0;
    vector<int> v;
    for(auto j:adj[i]){
        if(vis[j]||j==pr)continue;
        v.push_back(calc(j,i));
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int ma = 0;
    for(int j = 0;j<v.size();j++){
        ma = max(ma,v[j]+j+1);
    }
    return ma;
}
long long a,b,n;
bool can(long long mid){
    memset(vis,0,sizeof vis);
    int cur = b;
    int ti = 0;
    while(cur!=0){
        int ne = calc(cur,par[cur]);
        if(ne+ti<=mid){
            vis[cur] = 1;
            cur = par[cur];
            ti++;
        }else break;
    }
    if(calc(a,0)<=mid)return 1;
    else return 0;
}
signed 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);
    }
    dfs(a,0);
    long long l = 1 , r = 1e9 , ans = 0;
    while(l<=r){
        long long mid = (l+r)/2;
        if(can(mid))r = mid-1,ans = mid;
        else l = mid+1;
    }
    cout<<ans<<endl;
}

Compilation message

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

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 21452 KB Output is correct
2 Correct 781 ms 23912 KB Output is correct
3 Correct 699 ms 25280 KB Output is correct
4 Correct 790 ms 25044 KB Output is correct
5 Correct 820 ms 22564 KB Output is correct
6 Correct 662 ms 23772 KB Output is correct
7 Correct 601 ms 26388 KB Output is correct