Submission #86843

#TimeUsernameProblemLanguageResultExecution timeMemory
86843rzbtTorrent (COI16_torrent)C++14
100 / 100
210 ms49416 KiB
#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);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...