Submission #743332

#TimeUsernameProblemLanguageResultExecution timeMemory
743332alvingogoDuathlon (APIO18_duathlon)C++14
31 / 100
119 ms48084 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue #define int long long using namespace std; /* 1. tarjan find BCC(vertex) 2. block-cut tree type, size, subtree size 3. dp we iterate c square -> s, t aren't in the same subtree -> add to all the circle connecting to the square circle -> s, t aren't in the same subtree done? */ vector<vector<int> > e,bcc; vector<int> low,dfn,cv; int cnt=0,cc=0,cr=0; stack<int> st; void tj(int r,int f){ int sl=0; cnt++; dfn[r]=low[r]=cnt; st.push(r); for(auto h:e[r]){ if(h!=f){ if(!dfn[h]){ tj(h,r); sl++; low[r]=min(low[r],low[h]); if(low[h]>=dfn[r]){ if(f!=-1){ if(!cv[r]){ cr++; cv[r]=cr; } } bcc.push_back(vector<int>()); while(st.top()!=r){ bcc[cc].push_back(st.top()); st.pop(); } bcc[cc].push_back(st.top()); cc++; } } else{ low[r]=min(low[r],dfn[h]); } } } if(f==-1 && sl>=2){ if(!cv[r]){ cr++; cv[r]=cr; } } if(f==-1){ st.pop(); } } struct no{ vector<int> ch; int t=0,sq=0; long long tp=0; int sz=1; int vis=0; }; vector<no> v; long long ans=0; int dfs3(int r,int f){ v[r].vis=1; if(v[r].t){ v[r].sz=v[r].sq; } int k=v[r].sz; for(auto h:v[r].ch){ if(h!=f){ k+=dfs3(h,r); } } return k; } void dfs(int r,int f,int n){ for(auto h:v[r].ch){ if(h!=f){ dfs(h,r,n); v[r].sz+=v[h].sz; if(v[r].t){ v[r].tp+=1ll*v[h].sz*(v[h].sz-1); } } } if(v[r].t){ v[r].tp+=1ll*(n-v[r].sz)*(n-v[r].sz-1); ans-=1ll*v[r].sq*v[r].tp; } } void dfs2(int r,int f,int n){ for(auto h:v[r].ch){ if(h!=f){ dfs2(h,r,n); if(!v[r].t){ ans-=(v[h].tp-1ll*(n-v[h].sz)*(n-v[h].sz-1)); } } } if(!v[r].t){ ans-=(v[f].tp-1ll*(v[r].sz)*(v[r].sz-1)); } } signed main(){ AquA; int n; cin >> n; if(n<3){ cout << 0 << "\n"; return 0; } int m; cin >> m; e.resize(n); low.resize(n); dfn.resize(n); cv.resize(n); for(int i=0;i<m;i++){ int a,b; cin >> a >> b; a--; b--; e[a].push_back(b); e[b].push_back(a); } for(int i=0;i<n;i++){ if(!dfn[i]){ tj(i,-1); } } int s=cc; for(int i=0;i<n;i++){ if(cv[i]){ s++; } } v.resize(s); for(int i=0;i<cc;i++){ v[i].t=1; for(auto h:bcc[i]){ if(cv[h]){ v[i].ch.push_back(cv[h]+cc-1); v[cv[h]+cc-1].ch.push_back(i); } else{ v[i].sq++; } } } for(int i=0;i<cc;i++){ if(!v[i].vis){ int k=dfs3(i,i); ans+=1ll*k*(k-1)*(k-2); dfs(i,i,k); dfs2(i,i,k); } } cout << ans << "\n"; return 0; }
#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...