oj.uz

Submission #86843

# Submission time Handle Problem Language Result Execution time Memory
86843 2018-11-27T18:58:17 Z rzbt Torrent (COI16_torrent) C++14
100 / 100
 210 ms 49416 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14428 KB Output is correct
2 Correct 17 ms 14468 KB Output is correct
3 Correct 17 ms 14648 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 35312 KB Output is correct
2 Correct 182 ms 40124 KB Output is correct
3 Correct 157 ms 44992 KB Output is correct
4 Correct 173 ms 48160 KB Output is correct
5 Correct 201 ms 48160 KB Output is correct
6 Correct 162 ms 48160 KB Output is correct
7 Correct 156 ms 49416 KB Output is correct