#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
vector<int> v[N];
vector<int> v2[N];
vector<int> v3[N];
int in[N];
int low[N];
int t=1;
int num;
int sz[N];
bool cut[N];
stack<int> st;
void add_edge(int a,int b){
v2[a].eb(b);
v2[b].eb(a);
//debug(a,"<->",b);
}
void dfs(int x,int p=-1){
in[x]=low[x]=t++;
st.push(x);
bool ct=false;
for(int i:v[x]){
if(i==p) continue;
if(in[i]) low[x]=min(low[x],in[i]);
else{
dfs(i,x);
if(in[x]<=low[i]) ct=true;
low[x]=min(low[x],low[i]);
}
}
if(p==-1){
ct=(sz(v[x])>=2);
}
if(p==-1||in[p]<=low[x]){
++num;
while(sz(st)){
int x2=st.top();
st.pop();
add_edge(num,x2);
if(x2==x) break;
}
if(p!=-1)add_edge(num,p);
cut[num]=ct;
}
}
pii e[N];
int sum;
int n;
int Sz[N];
int Sz2[N];
bool vis[N];
int fa[N];
void dfs_sz(int x,int p=-1){
Sz[x]=sz[x];
for(int i:v2[x]){
if(i!=p){
dfs_sz(i,x);
Sz[x]+=Sz[i];
}
}
sum=Sz[x];
}
int C2(int x){
if(x<2) return 0;
return x*(x-1);
}
int C3(int x){
if(x<3) return 0;
return x*(x-1)*(x-2);
}
int ans=0;
void solve(int x,int p=-1){
fa[x]=p;
vis[x]=true;
for(int i:v2[x]){
if(!vis[i]) solve(i,x);
}
if(x<=n){
int a=sum-Sz[x];
int b=Sz[x]-1;
// debug("solve",x,Sz[x],a,b);
ans+=a*b*2;
int s=0;
for(int i:v2[x]){
if(fa[i]==x) ans+=C2(sz(v2[i])-1);
}
}
else{
for(int i:v2[x]){
if(fa[i]!=x){//Up
int Lft=sum-Sz[x];
// debug(x,"Add",i,"i",Lft,Lft*C2(sz(v2[x])-1)*2);
ans+=Lft*C2(sz(v2[x])-1)*2;
}
else{
int Lft=Sz[i]-1;
// debug(x,"Add",i,"i",Lft,Lft*C2(sz(v2[x])-1)*2);
ans+=Lft*C2(sz(v2[x])-1)*2;
}
}
}
}
signed main(){
quick
int m;
cin>>n>>m;
rep(i,1,m){
cin>>e[i].F>>e[i].S;
v[e[i].F].eb(e[i].S);
v[e[i].S].eb(e[i].F);
}
num=n;
dfs(1);
rep(i,1,n) sz[i]=1;
ans=0;
rep(i,1,num){
if(!vis[i]){
dfs_sz(i);
solve(i);
break;
}
}
//rep(i,1,n) cout<<Sz[i]<<" \n"[i==n];
cout<<ans<<"\n";
return 0;
}
Compilation message
count_triplets.cpp: In function 'void solve(long long int, long long int)':
count_triplets.cpp:107:7: warning: unused variable 's' [-Wunused-variable]
107 | int s=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
40788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
33628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
33612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
