Submission #1267903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267903		hoangmc2009	Torrent (COI16_torrent)	C++17	100 / 100	94 ms	24500 KiB

torrent

#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)));
    int l=0,r=pathAB.size()-2,mid,vl=calc2((pathAB.size()-2)/2,0);
    while(l<=r)
    {
        mid=(l+r)/2;
        if(calc2(mid,0)<vl) l=mid+1;
        else r=mid-1;
    }
    res=min(res,max(calc2(l,0),calc2(l+1,1)));
    l=0; r=pathAB.size()-2;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(calc2(mid,0)<=vl) l=mid+1;
        else r=mid-1;
    }
    res=min(res,max(calc2(r,0),calc2(r+1,1)));
    l=1; r=pathAB.size()-1; vl=calc2(pathAB.size()/2,1);
    while(l<=r)
    {
        mid=(l+r)/2;
        if(calc2(mid,1)>vl) l=mid+1;
        else r=mid-1;
    }
    res=min(res,max(calc2(l-1,0),calc2(l,1)));
    l=1; r=pathAB.size()-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(calc2(mid,1)>=vl) l=mid+1;
        else r=mid-1;
    }
    res=min(res,max(calc2(r-1,0),calc2(r,1)));
    cout<<res;
}
/*
                                                                                                   ........................
                                                                                            ..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::..
                                                                                  ..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+.
                                                                           ..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:.
                                                                     ..:-+*%@@@@@@@%%%##########################################%@@@@+:.
                                                                ..:=+%@@@@@@%%#####################################################@@@@+..
                                                          ....-+%@@@@@@%#############################################################@@@@=..
                                                        ..=#@@@@@%%###################################################################%@@@%-.
                                                    .:+#%@@@@%%#########################################################################%@@@#:.
                                                .:=*%@@@%%###############################################################################%@@@@-.
                                            ..-*%@@@%%#####################################################################################%@@@=.
                                          ..+@@@@###########################################################################################%@@@*..
                                         .*@@@#*##############################################################################################@@@%.
                                       .+@@@#**################################################################################################@@@%:.
                                     .-%@@#**####%##############################################################################################%@@%:.
                                    .+@@#***###%%################################################################################################%@@@-.
                                   :#@%****###%%*#################################################################################################%@@@-.
                                  -@@%****###@%*###################################################################################################%@@@-.
                                 -@@#***###%@#*#####################################################################################################%@@@=.
                                -@@#***###@@#*#######################################################################################################@@@%-.
                               :@@#***###@%**#########################################################################################################@@@+.
                              :%@#***##%@%**##########################################################################################################%@@@.
                             .#@%***##%@%**############################################################################################################%@@*.
                            .+@%***##@@#**##############################################################################################@@##############@@@:.
                            :@@***##@@#**###############################################################################################@@@%############%@@#.
                           .%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=.
                          .*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%.
                          -@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=.
                         .#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%.
                         =@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=.
                        .@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%.
                       .#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@-
                     ..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#.
                    .-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:.
                ...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*.
             ..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@.
          .#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+.
           :#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%.
            .+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-.
              .+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#.
                .:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:.
                 .....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*.
                     .=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@.
                     .%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=.
                    .+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%.
                    .@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=.
                   .+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%.
                   :@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+.
                  .*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:.
                  :@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#.
                 .*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*.
                .=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=.
                -@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=.
              .+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=.
            .-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+.
         ..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#.
    ...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-.
 .-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*..
 -@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=.
 .:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+.
   .+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:.
    .:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+.
      .+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+.
        .#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=.
         .-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-.
          ..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:.
             .=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=..
               .=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-.
                 .=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+..
                   .-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:.
                    ..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+..
                       .:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:.
                         ..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-.
                            .:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=..
                               .-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=..
                                ...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-..
                                   ...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:..
                                      ..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=..
                                          ..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:..
                                              ..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-.
                                                  ..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-..
                                                    .....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:...
                                                          ..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:..
                                                               ...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:..
                                                                     ...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:..
                                                                             ...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:..
                                                                               .*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:..
                                                                               .@@%****##########@#====%%###@##@%%%@@@%-:....
                                                                               -@@#****##########@#===+@#***@%=@%###@@%.
                                                                               =@@*****##########%@===#@#***%@=%@###%@@-
                                                                              .*@@*****###########@*==*%%%%%@@+@%###%@@+.
                                                                              .@@%****############%@+=====++==%@#####@@%.
                                                                              =@@#****#############@@========#@######@@@.
                                                                             .*@@*****############@@%@+=====*@#######@@@=.
                                                                             .%@@*****###########%@##@@#===#@########%@@*.
                                                                             -@@%****###########%@%##@%%%*#@##########@@%.
                                                                             =@@#****###########@%###@##%@@###########@@@-.
                                                                             +@@*****##########@@###%@##%@@###########@@@+.
                                                                            .%@@****##########@@####@%##%@@###########%@@%.
                                                                            -@@%****#########@@#####@###%@@############@@@:
                                                                            =@@#****########%@#####%@####@@############@@@=.
                                                                            #@@*****#######%@######@%####@@############%@@#.
                                                                           .%@@****#######%@######%@#####@@############%@@%.
                                                                           -@@%****######%@#######%@#####@@%############@@@-.
                                                                           =@@#****#####%@########@%#####@@%############@@@+.
                                                                           +@@#****####%@########%@######@@%############%@@#.
                                                                          .%@@****####%@#########@@######@@%############%@@@:
                                                                          :@@%****###%@##########@%######@@%#############@@@=.
                                                                          =@@%****##%%##########%@#######@@%#############@@@*.
                                                                          #@@#****#%%###########@@#######@@@#############%@@%.
                                                                         .%@@*****%############%@%#######@@@#############%@@@:
                                                                         -@@@****##############@@########%@@##############@@@+.
                                                                         -@@%****##############@%########%@@##############@@@#.
                                                                        .*@@#****#############@@#########%@@##############%@@@:
                                                                        .%@@*****#############@%#########%@@##############%@@@-.
                                                                        :@@@*****############%@##########%@@###############@@@*.
                                                                        -@@%*****############@%##########%@@###############@@@%.
                                                                        #@@#****############%@############@@###############%@@@:
                                                                       .%@@#****############@%############@@%###############@@@=.
                                                                       :@@@*****###########%@#############@@%###############@@@*.
                                                                       -@@%*****###########@%#############@@%###############@@@%.
                                                                       =@@%*****##########%@##############@@%###############%@@@:
                                                                      .#@@#*****##########@%##############@@%################@@@+.
                                                                      :@@@*****###########@###############@@%################@@@#.
*/

Compilation message (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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69