Submission #1185661

#TimeUsernameProblemLanguageResultExecution timeMemory
1185661PieArmyShymbulak (IZhO14_shymbulak)C++20
0 / 100
39 ms14908 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; int n; vector<int>komsu[200023]; int ans=0; ll num=0; int root[200023],dp[200023]; ll ways[200023]; int cycle(int pos,int las){ root[pos]=1; for(int x:komsu[pos]){ if(x==las)continue; if(root[x])return x; int y=cycle(x,pos); if(y==-1){ root[pos]=0; return -1; } if(y){ if(y==pos)return -1; return y; } } root[pos]=0; return 0; } void cal(int pos,int las){ ways[pos]=1; for(int x:komsu[pos]){ if(x==las)continue; if(root[x])continue; cal(x,pos); if(dp[x]+1+dp[pos]>ans){ num=0; ans=dp[x]+1+dp[pos]; } if(dp[x]+1+dp[pos]==ans){ num+=ways[x]*ways[pos]; } if(dp[x]+1>dp[pos]){ dp[pos]=dp[x]+1; ways[pos]=0; } if(dp[x]+1==dp[pos]){ ways[pos]+=ways[x]; } } } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; komsu[x].pb(y); komsu[y].pb(x); } cycle(1,1); vector<int>v; for(int i=1;i<=n;i++){ if(root[i]){ v.pb(i); cal(i,i); } } int cnt=v.size(); for(int i=0;i<cnt;i++){ v.pb(v[i]); } multiset<pair<int,ll>>st; for(int i=1;i<cnt/2;i++){ st.insert({dp[v[i]]+i,ways[v[i]]}); } for(int i=0;i<cnt;i++){ st.insert({dp[v[i+cnt/2]]+i+cnt/2,ways[v[i+cnt/2]]}); ll x=(--st.end())->fr-i+dp[v[i]],y=(--st.end())->sc*ways[v[i]]; if(ans<x){ ans=x; num=0; } if(ans==x){ num+=y; } st.erase(st.find({dp[v[i+1]]+i+1,ways[v[i+1]]})); } cout<<num<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...