oj.uz

답안 #846638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846638 2023-09-08T08:05:41 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 358 ms 41460 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e7;
ll n,a,b,x,y,check[300005],trace[300005],c,dist[300005],canh,moc,pos=-1,hao,res=mod;
vector<ll> ed[300005],pa,dp[300005];
void dfs(int u)
{
    check[u]=1;
    for (auto it: ed[u])
    {
        if (check[it]==0)
        {
            dfs(it);
            trace[it]=u;
        }
    }
}
void dpontree(int u,int v)
{
    dist[u]=0;
    if (u==v) return;
    check[u]=1;
    for (auto it: ed[u])
    {
        if (check[it]==0)
        {
            dpontree(it,v);
            dp[u].push_back(dist[it]);
        }
    }
    sort(dp[u].begin(),dp[u].end());
    canh=0;
    moc=1;
    for (int i=dp[u].size()-1;i>=0;--i)
    {
        canh=max(canh,dp[u][i]+moc);
        moc++;
    }
    dist[u]=canh;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>a>>b;
    c=b;
    for (int i=1;i<n;++i)
    {
        cin>>x>>y;
        ed[x].push_back(y);
        ed[y].push_back(x);
    }
    dfs(a);
    while (b!=0)
    {
        pa.push_back(b);
        b=trace[b];
    }
    b=c;
    int l=0,r=pa.size()-2;
    while (l<=r)
    {
        int mid=(l+r)/2;
        for (int i=1;i<=n;++i) dp[i].clear();
        memset(check,0,sizeof(check));
        dpontree(b,pa[mid+1]);
        dpontree(a,pa[mid]);
        res=min(res,max(dist[b],dist[a]));
        if (dist[b]<=dist[a])
        {
            l=mid+1;
        }
        else r=mid-1;
    }
//    if (pos==-1)
//    {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[1]);
//        cout<<dist[b];
//        return 0;
//    }
//    else
//    {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[pos+1]);
//        dpontree(a,pa[pos]);
//        hao=dist[a];
//        if (pos+2<pa.size())
//        {
//        for (int i=1;i<=n;++i) dp[i].clear();
//        memset(check,0,sizeof(check));
//        dpontree(b,pa[pos+2]);
//        dpontree(a,pa[pos+1]);
//        hao=min(hao,dist[b]);
//        }
//        cout<<hao;
//        return 0;
//    }
       cout<<res;
}

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 19544 KB Output is correct
2 Correct 4 ms 19548 KB Output is correct
3 Correct 5 ms 19544 KB Output is correct

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 39136 KB Output is correct
2 Correct 358 ms 40372 KB Output is correct
3 Correct 301 ms 40540 KB Output is correct
4 Correct 287 ms 40912 KB Output is correct
5 Correct 303 ms 39020 KB Output is correct
6 Correct 290 ms 39112 KB Output is correct
7 Correct 250 ms 41460 KB Output is correct