Submission #1197893

#TimeUsernameProblemLanguageResultExecution timeMemory
1197893nikolashamiDuathlon (APIO18_duathlon)C++20
0 / 100
83 ms33092 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; #define pb push_back const ll N=1e5+2; vector<ll>g[N],f[N],ob[N],bck[N]; ll vs[N],up[N],dep[N],par[N],col[N],ar[N],w[N],sz[N],ar2[N],cr,ans; void dfst(ll u){ vs[u]=1; for(ll v:g[u]){ if(vs[v]){ bck[u].pb(v); bck[v].pb(u); }else{ ob[u].pb(v); ob[v].pb(u); dfst(v); } } } void gd(ll u,ll p){ par[u]=p; for(ll v:ob[u]){ if(!(v^p))continue; dep[v]=dep[u]+1; gd(v,u); } } void dfsa(ll u,ll p){ up[u]=N; ll mx=0; for(ll v:ob[u]){ if(!(v^p))continue; dfsa(v,u); up[u]=min(up[u],up[v]); mx=max(mx,up[v]); } if(mx>=dep[u]&&ob[u].size()>1)ar[u]=1; for(ll v:bck[u]) up[u]=min(up[u],dep[v]); } ll cnt; void dfsc(ll u){ vs[u]=1; col[u]=cr; ++cnt; for(ll v:g[u]){ if(vs[v]||ar[v])continue; dfsc(v); } } void get(ll u,ll p){ if(u==1)dep[u]=w[u]; sz[u]=w[u]; par[u]=p; for(ll v:f[u]){ if(!(v^p))continue; dep[v]=dep[u]+w[v]; get(v,u); sz[u]+=sz[v]; } } void dfs(ll u,ll p){ ll s=0; for(ll v:f[u]){ if(!(v^p))continue; s+=sz[v]; } ll tmp=ans; ans+=(w[u]-1)*dep[par[u]]*2*w[u]; for(ll v:f[u]){ if(!(v^p))continue; ans+=(w[u]-1)*sz[v]*2*w[u]; ans+=(dep[par[u]])*sz[v]*2*w[u]; ans+=sz[v]*(s-sz[v])*2*w[u]; ans+=w[v]*(w[v]-1)*w[u]; } ans+=(w[u]-1)*(w[u]-2)*w[u]; ans+=(w[par[u]])*(w[par[u]]-1)*w[u]; ll delta=ans-tmp; //cout<<u<<' '<<delta<<endl; for(ll v:f[u]){ if(v^p)dfs(v,u); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); ll n,m; cin>>n>>m; for(int i=1,u,v;i<=m;++i){ cin>>u>>v; g[u].pb(v); g[v].pb(u); } dfst(1); gd(1,0); dfsa(1,0); fill(vs,vs+n+1,0); for(int i=1;i<=n;++i){ if(!ar[i])continue; for(int j:g[i]){ if(!vs[j]&&!ar[j]){ ++cr; cnt=0; dfsc(j); cr-=!cnt; } } } for(int i=1;i<=n;++i){ if(ar[i])col[i]=++cr; ar2[cr]=1; } for(int i=1;i<=n;++i) ++w[col[i]]; set<ll>ss; for(int i=1;i<=n;++i){ if(!ar[i])continue; ss.clear(); for(int j:g[i]){ if(ss.find(col[j])!=ss.end())continue; ss.insert(col[j]); f[col[i]].pb(col[j]); if(!ar[j])f[col[j]].pb(col[i]); } } get(1,0); dfs(1,0); bool ok=0; for(int i=1;i<=n;++i)ok|=ar[i]; if(!ok)ans=n*(n-1)*(n-2); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...