#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){
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){
cv[r]=1;
}
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 n;
void dfs(int r,int f){
v[r].vis=1;
if(v[r].t){
v[r].sz=v[r].sq;
}
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
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){
for(auto h:v[r].ch){
if(h!=f){
dfs2(h,r);
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;
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);
}
tj(0,-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){
dfs(i,i);
ans+=1ll*v[i].sz*(v[i].sz-1)*(v[i].sz-2);
dfs2(i,i);
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
21048 KB |
Output is correct |
| 2 |
Correct |
55 ms |
21020 KB |
Output is correct |
| 3 |
Incorrect |
43 ms |
14668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
91 ms |
47720 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
47648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
316 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
