Submission #548930

#TimeUsernameProblemLanguageResultExecution timeMemory
548930leakedDuathlon (APIO18_duathlon)C++17
0 / 100
84 ms26908 KiB
#include <bits/stdc++.h> #define f first #define s second #define m_p make_pair #define vec vector #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) #define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef pair<int,int> pii; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; typedef unsigned long long ull; //#define int long long template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);} template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);} const int N=1e5+1; struct dsu{ int p[N]; int cnt[N]; dsu(){ iota(p,p+N,0); fill(cnt,cnt+N,1); } int get(int v){ return p[v]=(p[v]==v?v:get(p[v])); } void mg(int a,int b){ a=get(a),b=get(b); if(a==b) return; p[a]=b;cnt[b]+=cnt[a]; } }xy; vec<int> gr[N],g[N]; int sub[N]; int in[N],fup[N],tt=1; int cnt=0; vec<pii> e; void dfs1(int v,int p){ in[v]=fup[v]=tt++; ++cnt; for(auto &z : g[v]){ if(z==p) continue; if(in[z]){ umin(fup[v],in[z]); continue; } dfs1(z,v); umin(fup[v],fup[z]); if(fup[z]<=in[v]) xy.mg(v,z); else e.pb({v,z}); // cout<<"WOT "<<(fup[z]<=in[v])<<' '<<v<<' '<<z<<endl; } } ll dp[N][2]; ll up[N][2]; ll wow[N]; void dfs2(int v,int p){ dp[v][0]+=xy.cnt[v]; ll have=xy.cnt[v]; for(auto &z : gr[v]){ dfs2(z,v); dp[v][0]+=dp[z][0]; dp[v][1]+=dp[z][1]; dp[v][1]+=2ll*dp[z][0]*have; have+=dp[z][0]; } // cout<<"WOW "<<v<<' '<<dp[v][1]<<endl; } ll bad=0; void dfs3(int v){ bad+=dp[v][1]+up[v][1]; // cout<< ll have=cnt-dp[v][0]+xy.cnt[v]; bad+=2ll*(xy.cnt[v]-1)*(cnt-dp[v][0]); ll par=2ll*(cnt-dp[v][0])*xy.cnt[v]; bad-=1ll*(xy.cnt[v])*(cnt-xy.cnt[v]); // cout<<"WAT "<<v<<' '<<bad<<' '<<xy.cnt[v]-1<<' '<<cnt-dp[v][0]<<endl; for(auto &z : gr[v]){ par+=2ll*dp[z][0]*have; have+=dp[z][0]; bad+=2ll*(xy.cnt[v]-1)*(dp[z][0]); } // cout<<"WOW "<<par<<' '<<up[v][1]<<' '<<have<<endl; for(auto &z : gr[v]){ up[z][1]=par-(2ll*(have-dp[z][0])*(dp[z][0]))+up[v][1]; dfs3(z); } } signed main(){ fast_prep; int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int v,u; cin>>v>>u; g[v].pb(u);g[u].pb(v); } // for(int i=1;i<=n;i++) dp[i][0]=1; ll total=0; for(int i=1;i<=n;i++){ if(!in[i]){ dfs1(i,i); for(auto &z : e){ // cout<<"G "<<xy.get(z.f)<<' '<<xy.get(z.s)<<endl; gr[xy.get(z.f)].pb(xy.get(z.s)); } dfs2(xy.get(i),xy.get(i)); dfs3(xy.get(i)); // cout<<cnt<<''endl; total+=1ll*cnt*(cnt-1)*(cnt-2)-bad; bad=0; cnt=0;e.clear(); } } cout<<total; return 0; } /* abbaaa cbbbbccbbccbbbbbbc (((((((()))()))))) 5 5 4 2 2 5 4 1 2 1 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...