oj.uz

Submission #952467

# Submission time Handle Problem Language Result Execution time Memory
952467 2024-03-24T03:25:45 Z vjudge1 Torrent (COI16_torrent) C++17
69 / 100
 300 ms 29468 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 5<<16
vector<int>adj[N],path;
int dp[N],par[N],a,b,cut,ans=1e9;
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];
    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:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10584 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 266 ms 22820 KB Output is correct
2 Correct 299 ms 24796 KB Output is correct
3 Correct 290 ms 27652 KB Output is correct
4 Correct 300 ms 25664 KB Output is correct
5 Correct 266 ms 22672 KB Output is correct
6 Correct 273 ms 23360 KB Output is correct
7 Correct 264 ms 29468 KB Output is correct