제출 #846666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846666		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	614 ms	27312 KiB

torrent

#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;
////
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 31
• Subtask 2: 69 / 69