Submission #260926

#TimeUsernameProblemLanguageResultExecution timeMemory
260926emanIaicepsaDuathlon (APIO18_duathlon)C++14
31 / 100
192 ms24568 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,ll> #define vi vector<int> #define pb emplace_back #define fi first #define se second #define all(n) (n).begin(),(n).end() #define mem(n,m) memset(n,m,sizeof(n)) #define IOS ios::sync_with_stdio(0), cin.tie(0) #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__); template<typename A> void _do(A x){cerr<<x<<'\n';} template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);} const int mxn = 100005; ll C(ll x){ return (x)*(x-1)*(x-2)/6*2; } ll P(ll x){ return C(x)*3; } ll n,m; vi E[mxn], E2[mxn]; ll siz[mxn], ans=0, l[mxn], d[mxn], bcc[mxn], bcc_siz[mxn], dfn, bccid, vis[mxn], rt[mxn]; stack<int> s; void dfs(int x,int p){ l[x] = d[x] = ++dfn; s.push(x); for(auto i:E[x]){ if(i==p) continue; if(!d[i]){ dfs(i,x); l[x] = min(l[x],l[i]); } else{ l[x] = min(l[x],d[i]); } } if(l[x] == d[x]){ bccid++; for(int i;i!=x;){ i = s.top(); s.pop(); bcc[i] = bccid; } } } void bcc_dfs(int x,int p,int anc){ rt[x] = anc; siz[x] = bcc_siz[x]; vis[x] = 1; for(auto i:E2[x]){ if(i==p) continue; bcc_dfs(i,x,anc); siz[x] += siz[i]; } } void bcc_dfs2(int x,int p,int anc){ vis[x] = 1; for(auto i:E2[x]){ if(i==p) continue; bcc_dfs2(i,x,anc); ans += siz[i] * (siz[anc] - siz[i] - bcc_siz[x]) * bcc_siz[x]; } ans += (siz[x]-bcc_siz[x]) * (siz[anc]-siz[x]); } signed main(){ IOS; cin>>n>>m; for(int i=1,a,b;i<=m;i++){ cin>>a>>b; E[a].pb(b); E[b].pb(a); } for(int i=1;i<=n;i++) if(!d[i]) dfs(i,0); for(int i=1;i<=n;i++){ //dbg(i, bcc[i]); bcc_siz[bcc[i]]++; for(auto j:E[i]){ if(bcc[i] == bcc[j]) continue; E2[bcc[i]].pb(bcc[j]); E2[bcc[j]].pb(bcc[i]); } } for(int i=1;i<=bccid;i++){ sort(all(E2[i])); E2[i].resize(unique(all(E2[i]))-E2[i].begin()); } for(int i=1;i<=bccid;i++){ if(!vis[i]){ bcc_dfs(i,0,i); } } // for(int i=1;i<=bccid;i++){ // dbg(i, siz[i]); // } mem(vis,0); for(int i=1;i<=bccid;i++){ if(bcc_siz[i]>=3){ ll x = bcc_siz[i]; ans += P(x); ans += (x-1) * (x-1) * (siz[rt[i]] - x) * 2; } if(!vis[i]){ bcc_dfs2(i,0,i); } } cout<<ans<<'\n'; } /* 3 3 1 2 2 3 3 1 4 4 1 2 2 3 3 4 2 4 5 4 1 2 2 3 1 3 4 5 */
#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...