Submission #86843

#	Time	Username	Problem	Language	Result	Execution time	Memory
86843		rzbt	Torrent (COI16_torrent)	C++14	100 / 100	210 ms	49416 KiB

torrent

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 300005
typedef long long ll;


using namespace std;

int n,a,b;
vector<int> niz[MAXN];
int los[MAXN],otac[MAXN];
vector<int> zbirovi[MAXN];
vector<int> kriticni;


bool dfsinit(int t,int o){
    otac[t]=o;
    if(t==b){

        los[b]=o;
        return true;
    }
    for(auto x:niz[t]){
        if(x==o)continue;
        if(dfsinit(x,t)){
            los[t]=x;
            if(t!=a)kriticni.pb(t);
            return true;
        }
    }
    return false;
}

int dfs1(int t,int o){

    for(auto x:niz[t]){
        if(x==o || los[t]==x)continue;
        zbirovi[t].pb(dfs1(x,t));
    }
    sort(all(zbirovi[t]),greater<int>());
    for(int i=0;i<zbirovi[t].size();i++)zbirovi[t][i]+=i+1;
    int mx=0;
    for(auto x:zbirovi[t])mx=max(x,mx);
    //printf("   %d %d        %d\n",t,o,mx+1);
    return mx;
}



int main()
{
    scanf("%d %d %d", &n, &a, &b);
    for(int i=1;i<n;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        niz[t1].pb(t2);
        niz[t2].pb(t1);
    }
    dfsinit(a,0);
    int res=max(dfs1(a,0),dfs1(b,otac[b]))+1;

    //printf("     lepetije lepetije\n");


    for(int i=0;i<kriticni.size();i++)res=max(res,min(1+i,(int)kriticni.size()-i)+dfs1(kriticni[i],otac[kriticni[i]]));
    if(kriticni.empty())res--;
    printf("%d",res);
    return 0;
}
/*
Typical effects of MDMA include anxiety relief, disinhibition, enhanced empathy and sociability, relaxation, and euphoria. MDMA is classified as an entactogen due to how it facilitates feelings of closeness with oneself and others. It is commonly associated with dance parties, raves, and electronic dance music
*/

Compilation message (stderr)

torrent.cpp: In function 'int dfs1(int, int)':
torrent.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<zbirovi[t].size();i++)zbirovi[t][i]+=i+1;
                 ~^~~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<kriticni.size();i++)res=max(res,min(1+i,(int)kriticni.size()-i)+dfs1(kriticni[i],otac[kriticni[i]]));
                 ~^~~~~~~~~~~~~~~~
torrent.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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