| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 404314 | 2021-05-14T07:28:26 Z | kshitij_sodani | Ancient Books (IOI17_books) | C++14 | 0 ms | 0 KB |
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,m;
vector<llo> adj[100001];
llo vis[100001];
llo par[100001];
llo ind[100001];
vector<llo> ss;
set<llo> adj2[100001];
llo val[100001];
vector<llo> pre[100001];
llo par5[100001];
llo lev[100001];
void dfs(llo no,llo par2=-1,llo levv=0){
ss.pb(no);
vis[no]=1;
par5[no]=par2;
par[no]=no;
lev[no]=levv;
for(auto j:adj[no]){
if(j!=par2){
if(vis[j]==0){
dfs(j,no,levv+1);
}
else if(lev[j]<lev[no]){
vector<llo> cot;
llo cur=no;
while(cur!=j){
cot.pb(cur);
cur=par5[cur];
}
cot.pb(cur);
for(auto ii:cot){
par[ii]=j;
}
}
}
}
}
llo par3[100001];
llo ans=0;
void dfs2(llo no,llo par2=-1){
par3[no]=par2;
//val[no]=1;
//ss.pb(no);
// vis[no]=1;
llo su=0;
for(auto j:adj2[no]){
if(j!=par2){
dfs2(j,no);
su+=val[j];
val[no]+=val[j];
}
}
for(auto j:adj2[no]){
if(j!=par2){
//cout<<no<<":"<<j<<":"<<(val[j]*(su-val[j])*(val[no]-su))<<endl;
ans+=(val[j]*(su-val[j])*(val[no]-su));
}
}
}
llo pa=-1;
llo co5=0;
llo vis2[100001];
void dfs3(llo no){
vis2[no]=1;
co5++;
for(auto j:adj[no]){
if(vis2[j]==0 and par[j]!=pa){
dfs3(j);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<m;i++){
llo aa,bb;
cin>>aa>>bb;
aa--;
bb--;
adj[aa].pb(bb);
adj[bb].pb(aa);
}
for(llo i=0;i<n;i++){
if(vis[i]==0){
ss.clear();
//dfs2(i);
/* for(auto j:ss){
ans+=2*(val[j]-1)*(ss.size()-val[j]);
//cout<<j<<":";
}*/
//cout<<endl;
//continue;
dfs(i);
for(auto j:ss){
val[par[j]]++;
for(auto ii:adj[j]){
if(par[j]!=par[ii]){
adj2[par[j]].insert(par[ii]);
}
}
}
//continue;
for(auto j:ss){
pre[par[j]].pb(j);
}
dfs2(i);
/*for(auto j:ss){
cout<<j<<":"<<par[j]<<":"<<val[j]<<endl;
}*/
llo nn=ss.size();
for(auto j:ss){
if(par[j]==j){
llo aa=pre[j].size();
if(aa>=3){
ans+=((((aa*(aa-1)*(aa-2)))));
}
ans+=2*(val[j]-aa)*aa*(nn-val[j]);
//continue;
llo co2=0;
if(aa>=2){
for(auto ii:ss){
vis2[ii]=0;
}
for(auto ii:pre[j]){
pa=par[ii];
co5=0;
dfs3(ii);
ans+=2*((co5-1)*(aa-1)*(aa-1));
//cout<<ii<<":"<<co5<<endl;
//cout<<ii<<":"<<co5[ii]<<endl;
// cout<<ii<<":"<<(aa-1)*2*(ss.size()-co5-(aa-1))<<endl;
// ans+=(aa-1)*2*(ss.size()-co5-(aa-1));
continue;
if(ii!=j){
llo co=ss.size();
co-=aa;
for(auto k:adj[ii]){
if(k!=par5[ii] and par[k]!=par[ii]){
co-=val[k];
co2+=val[k];
}
}
ans+=2*(aa-1)*co;
// cout<<ii<<":"<<(2*(aa-1))*co<<":"<<co<<endl;
}
}
//ans+=2*(aa-1)*co2;
//cout<<j<<":"<<(2*(aa-1))*co2<<endl;
}
}
}
}
}
cout<<ans<<endl;
// dfs(0);
return 0;
}