oj.uz

Submission #846665

# Submission time Handle Problem Language Result Execution time Memory
846665 2023-09-08T08:38:13 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 588 ms 27192 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second

const int ar=3e5+5;
const ll mod=1e9+7;
int n,a,b;
vector<int> ad[ar];
vector<pair<int,int>> ed;
bool d[ar];
int p[ar];
void dfs(int u)
{
    d[u]=true;
    for (auto v:ad[u])
    {
        if (!d[v])
        {
            p[v]=u;
            dfs(v);
        }
    }
}
int dp[2][ar];
bool ok[ar];
void solve(int u,int pa,int type)
{
    vector<int> child;
    for (auto v:ad[u])
    {
        if (v!=pa && !ok[v])
        {
            solve(v,u,type);
            child.push_back(dp[type][v]);
        }
    }
    sort(child.begin(),child.end(),greater<int>());
    for (int i=0;i<child.size();i++)
    {
        dp[type][u]=max(dp[type][u],child[i]+i+1);
    }
    //child.clear();
}
int ans=1e9;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>a>>b;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    dfs(a);
    int cur=b;
    while(cur!=a)
    {
        ed.push_back({cur,p[cur]});
        cur=p[cur];
    }
    int l=0;
    int r=ed.size()-1;
    while(l<=r)
    {
        memset(dp,0,sizeof dp);
        int m=l+r>>1;
        ok[ed[m].fi]=true;
        solve(a,0,0);
        ok[ed[m].fi]=false;
        ok[ed[m].se]=true;
        solve(b,0,1);
        ok[ed[m].se]=false;
        if (dp[0][a]>=dp[1][b])
        {
            ans=min(ans,dp[0][a]);
            l=m+1;
        }
        else r=m-1;
        //ok[ed[m].fi]=ok[ed[m].se]=false;
    }
    l=0;
    r=ed.size()-1;
    while(l<=r)
    {
        memset(dp,0,sizeof dp);
        int m=l+r>>1;
        ok[ed[m].fi]=true;
        solve(a,0,0);
        ok[ed[m].fi]=false;
        ok[ed[m].se]=true;
        solve(b,0,1);
        ok[ed[m].se]=false;
        if (dp[0][a]<=dp[1][b])
        {
            ans=min(ans,dp[1][b]);
            r=m-1;
        }
        else l=m+1;
        //ok[ed[m].fi]=ok[ed[m].se]=false;
    }
    cout<<ans;
}

Compilation message

torrent.cpp: In function 'void solve(int, int, int)':
torrent.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i=0;i<child.size();i++)
      |                  ~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:71:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int m=l+r>>1;
      |               ~^~
torrent.cpp:91:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int m=l+r>>1;
      |               ~^~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 23544 KB Output is correct
2 Correct 588 ms 25260 KB Output is correct
3 Correct 451 ms 26824 KB Output is correct
4 Correct 473 ms 26308 KB Output is correct
5 Correct 498 ms 23100 KB Output is correct
6 Correct 457 ms 23604 KB Output is correct
7 Correct 461 ms 27192 KB Output is correct