Submission #1183607

#TimeUsernameProblemLanguageResultExecution timeMemory
1183607ziyad_alharbiHard route (IZhO17_road)C++20
0 / 100
39 ms12104 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,s; set<int>st,rm; vector<int>v[500000]; array<int,2>ans; bool bln; bool f(int i,int o,int j) { rm.insert(i); if(i==j)return bln=1; for(auto x:v[i]) { if(x==o)continue; f(x,i,j); if(bln)return bln=1; } if(bln)return bln=1; rm.erase(i); return bln=0; } void bfs() { queue<array<int,3>>q; for(int x=1;x<=n;x++)q.push({x,0,0}); int mx=0; while(q.size()) { auto [i,sz,o]=q.front(); q.pop(); mx=sz; if(rm.count(i))continue; for(auto j:v[i]) { if(j==o)continue; q.push({j,sz+1,i}); } } if(mx*s>ans[0])ans={mx*s,1}; else if(mx*s==ans[0])ans[1]++; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int x=0;x<n-1;x++) { int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } ans={0,0}; for(int x=1;x<=n;x++)if(v[x].size()==1)st.insert(x); for(auto i:st) { for(auto j:st) { if(j<=i)continue; rm.clear(); bln=0; f(i,0,j); s=rm.size()-1; bfs(); } } cout<<ans[0]<<' '<<ans[1]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...