제출 #1267896

#제출 시각아이디문제언어결과실행 시간메모리
1267896hoangmc2009Torrent (COI16_torrent)C++17
31 / 100
2097 ms23228 KiB
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n,A,B,par[300009],inpAB[300009],res=2e9;
vector<int> adj[300009];
struct pathVal
{
    int v,s; vector<int> cs;
    pathVal(int vv):cs(0){v=vv;s=0;}
};
vector<pathVal> pathAB;
void GetPar(int u,int pu)
{
    par[u]=pu;
    for(int& v:adj[u])
        if(v!=pu) GetPar(v,u);
}
int calc(int u,int pu)
{
    int mx=0; vector<int> tmp;
    for(int& v:adj[u])
    {
        if(v==pu or inpAB[u]&inpAB[v]) continue;
        tmp.push_back(calc(v,u));
    }
    sort(tmp.begin(),tmp.end(),greater<int>());
    for(int i=0;i<tmp.size();++i) mx=max(mx,tmp[i]+i+1);
    return mx;
}
int calc2(int p,bool AB) //0:A, 1:B
{
    int mx=pathAB[p].s;
    if(AB)
    {
        for(int i=p+1;i<pathAB.size();++i)
        {
            if(pathAB[i].cs.empty()) ++mx;
            else
            {
                int tmp=0;
                for(int ok=0,c=0,j=0;j<pathAB[i].cs.size();++j)
                {
                    if(pathAB[i].cs[j]<mx and !ok) tmp=max(tmp,mx+(++c)),ok=1;
                    tmp=max(tmp,pathAB[i].cs[j]+(++c));
                }
                mx=tmp;
            }
        }
    }
    else
    {
        for(int i=p-1;i>=0;--i)
        {
            if(pathAB[i].cs.empty()) ++mx;
            else
            {
                int tmp=0;
                for(int ok=0,c=0,j=0;j<pathAB[i].cs.size();++j)
                {
                    if(pathAB[i].cs[j]<mx and !ok) tmp=max(tmp,mx+(++c)),ok=1;
                    tmp=max(tmp,pathAB[i].cs[j]+(++c));
                }
                mx=tmp;
            }
        }
    }
    return mx;
}
int main()
{
    if(fopen("TDL.INP","r"))
    {
        freopen("TDL.INP","r",stdin);
        freopen("TDL.OUT","w",stdout);
    }
    else if(fopen("D:/CPP/THEMIS/test.inp","r"))
    {
        freopen("D:/CPP/THEMIS/test.inp","r",stdin);
        freopen("D:/CPP/THEMIS/test.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B;
    for(int u,v,i=1;i<n;++i)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    GetPar(A,0);
    for(int i=B;i!=A;i=par[i])
    {
        pathAB.push_back(pathVal(i));
        inpAB[i]=1;
    }
    pathAB.push_back(pathVal(A)); inpAB[A]=1;
    reverse(pathAB.begin(),pathAB.end());
    for(int i=0;i<pathAB.size();++i)
    {
        pathAB[i].s=calc(pathAB[i].v,0);
        for(int& u:adj[pathAB[i].v])
            if(!inpAB[u]) pathAB[i].cs.push_back(calc(u,pathAB[i].v));
        sort(pathAB[i].cs.begin(),pathAB[i].cs.end(),greater<int>());
    }
    for(int i=1;i<pathAB.size();++i)
        res=min(res,max(calc2(i-1,0),calc2(i,1)));
    cout<<res;
}

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

torrent.cpp: In function 'int main()':
torrent.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen("TDL.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("TDL.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("D:/CPP/THEMIS/test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("D:/CPP/THEMIS/test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...