제출 #1198383

#제출 시각아이디문제언어결과실행 시간메모리
1198383nikolashami철인 이종 경기 (APIO18_duathlon)C++20
100 / 100
122 ms58808 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; #define pb push_back const ll N=2e5+4; vector<ll>g[N],f[N],ob[N],bck[N],comp[N],cur,ljudi; ll vs[N],up[N],dep[N],col[N],ar[N],sz[N],naj[N],n,m,cr,ans; void dfst(ll u){ ljudi.push_back(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){ sz[u]=1; for(ll v:ob[u]){ if(!(v^p))continue; dep[v]=dep[u]+1; gd(v,u); sz[u]+=sz[v]; } } void dfsa(ll u,ll p){ up[u]=N; cur.push_back(u); for(ll v:ob[u]){ if(!(v^p))continue; dfsa(v,u); up[u]=min(up[u],up[v]); if(up[v]>=dep[u]){ ar[u]|=1; ++cr; comp[cr].push_back(u); while(cur.back()!=v){ comp[cr].push_back(cur.back()); cur.pop_back(); } comp[cr].push_back(v); cur.pop_back(); } } for(ll v:bck[u]) up[u]=min(up[u],dep[v]); } void dfs3(ll u,ll p){ sz[u]=1; if(u>n)--sz[u]; for(ll v:f[u]){ if(!(v^p))continue; dfs3(v,u); sz[u]+=sz[v]; if(u<=n)continue; ans-=(sz[v])*(sz[v]-1)*(f[u].size()-1); } if(u<=n)return; ans-=(ljudi.size()-sz[u])*(ljudi.size()-sz[u]-1)*(f[u].size()-1); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1,u,v;i<=m;++i){ cin>>u>>v; g[u].pb(v); g[v].pb(u); } for(int i=1;i<=n;++i){ if(vs[i])continue; cur.clear(); ljudi.clear(); cr=0; dfst(i); ans+=ljudi.size()*(ljudi.size()-1)*(ljudi.size()-2); gd(i,i); dfsa(i,i); for(int j=1;j<=cr;++j){ for(ll k:comp[j]){ f[k].push_back(n+j); f[n+j].push_back(k); } } dfs3(i,i); for(int j=1;j<=cr;++j){ for(ll k:comp[j]){ if(f[k].size())f[k].clear(); if(f[n+j].size())f[n+j].clear(); } comp[j].clear(); } for(ll j:ljudi)assert("jbt"); } for(int i=1;i<=cr&&0;++i){ cout<<"comp#"<<i<<endl; cout<<"[\n"; for(auto j:comp[i])cout<<j<<endl; cout<<"]\n"; } 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...