oj.uz

Submission #952464

# Submission time Handle Problem Language Result Execution time Memory
952464 2024-03-24T03:16:14 Z vjudge1 Torrent (COI16_torrent) C++17
69 / 100
 321 ms 56212 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 1<<20
vector<int>adj[N],path;
int dp[N],par[N],a,b,cut,ans=N;
void BT(int n){
    for(auto i:adj[n])
        if(i-par[n])
            par[i]=n,BT(i);
}
void dfs(int n,int p){
    dp[n]=0;
    vector<int>kirby;
    for(auto i:adj[n]) if(i-p&&i-cut)
        dfs(i,n),kirby.push_back(dp[i]);
    sort(kirby.rbegin(),kirby.rend());
    for(int i=0;i<kirby.size();i++)
        dp[n]=max(dp[n],kirby[i]+i+1);
}
bool check(int x,int y){
    cut=x;
    dfs(a,0);
    cut=y;
    dfs(b,0);
    ans=min(ans,max(dp[a],dp[b]));
    return dp[a]<dp[b];
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n>>a>>b;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    BT(a);
    dfs(a,0);
    ans=dp[a];
    if(a==b){
        cout<<ans;
        exit(0);
    }
    int b2=b;
    while(b2-a)
        path.push_back(b2),b2=par[b2];
    path.push_back(a);
    int l=0,r=path.size()-2;
    while(l<=r){
        int mid=l+r>>1;
        if(check(path[mid],path[mid+1]))
            l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<kirby.size();i++)
      |                 ~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 29020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 48648 KB Output is correct
2 Correct 321 ms 50480 KB Output is correct
3 Correct 301 ms 54356 KB Output is correct
4 Correct 317 ms 51608 KB Output is correct
5 Correct 267 ms 48160 KB Output is correct
6 Correct 274 ms 49408 KB Output is correct
7 Correct 275 ms 56212 KB Output is correct