제출 #536467

#제출 시각아이디문제언어결과실행 시간메모리
536467nicholask철인 이종 경기 (APIO18_duathlon)C++14
31 / 100
201 ms27640 KiB
#include <bits/stdc++.h> #define int long long #define x first #define y second #define pb push_back using namespace std; using pii=pair <int,int>; int n,m; vector <int> g[100010],bc[200020]; bool visited[200010]; int tme,dfn[200020],low[200020],curid; stack <int> st; int weigh[200020]; void dfs(int cur){ tme++; dfn[cur]=tme; low[cur]=tme; st.push(cur); visited[cur]=1; for (int i:g[cur]){ if (!visited[i]){ dfs(i); low[cur]=min(low[cur],low[i]); if (low[i]==dfn[cur]){ curid++; while (st.top()!=cur){ bc[st.top()].pb(curid); bc[curid].pb(st.top()); st.pop(); weigh[curid]++; } bc[cur].pb(curid); bc[curid].pb(cur); weigh[curid]++; } } else low[cur]=min(low[cur],dfn[i]); } } int ans,rtsz; int siz[200020]; void dfs2(int cur,int prv){ siz[cur]=(cur<=n); for (int i:bc[cur]){ if (i==prv) continue; dfs2(i,cur); siz[cur]+=siz[i]; } if (prv==-1) rtsz=siz[cur]; } void dfs3(int cur,int prv){ if (cur<=n){ int ww=(rtsz-1)*(rtsz-1),sum=0; for (int i:bc[cur]){ if (i==prv) continue; ww-=siz[i]*siz[i]; sum+=siz[i]; } ww-=(rtsz-sum-1)*(rtsz-sum-1); ww/=2; ww+=(rtsz-1); ans-=max(0ll,ww); } else { int ww=rtsz*rtsz,sum=0; for (int i:bc[cur]){ if (i==prv) continue; ww-=siz[i]*siz[i]; sum+=siz[i]; } ww-=(rtsz-sum)*(rtsz-sum); ww/=2; ans+=max(0ll,ww)*weigh[cur]; } for (int i:bc[cur]){ if (i==prv) continue; dfs3(i,cur); } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; while (m--){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } curid=n; for (int i=1; i<=n; i++){ if (visited[i]) continue; dfs(i); while (!st.empty()) st.pop(); dfs2(i,-1); dfs3(i,-1); } cout<<2*ans<<'\n'; }
#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...