제출 #1184100

#제출 시각아이디문제언어결과실행 시간메모리
1184100ziyad_alharbiHard route (IZhO17_road)C++20
19 / 100
2105 ms196880 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,ds[5005][5005],vs[5005],g1,g2; set<int>st,rm; vector<int>v[5005]; array<int,2>ans; 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); } for(int x=1;x<=n;x++)if(v[x].size()==1)st.insert(x); memset(ds,-1,sizeof ds); for(int x=1;x<=n;x++) { queue<array<int,2>>q; q.push({x,0}); while(q.size()) { auto [i,sz]=q.front(); q.pop(); ds[x][i]=sz; for(auto j:v[i])if(ds[x][j]==-1)q.push({j,sz+1}); } } for(auto i:st) { for(auto j:st) { if(i>=j)continue; g1=i; g2=j; rm.clear(); for(int x=1;x<=n;x++)vs[x]=0; queue<int>q; q.push(i); vs[i]=-1; while(q.size()) { int x=q.front(); q.pop(); if(x==j)break; for(auto vr:v[x]) { if(vs[vr])continue; vs[vr]=x; q.push(vr); } } int jh=j; while(jh!=-1) { rm.insert(jh); jh=vs[jh]; } int mx=0,vl=0; for(int x=1;x<=n;x++) { int mn=1e9; vl+=rm.count(x); for(auto ii:rm) { mn=min(mn,ds[x][ii]); } mx=max(mx,mn); } int sz=rm.size()-1; if(mx*sz>ans[0])ans={mx*sz,1}; else if(mx*sz==ans[0])ans[1]++; } } 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...