#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){
cr++;
cv[r]=cr;
}
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 dfs3(int r,int f){
v[r].vis=1;
if(v[r].t){
v[r].sz=v[r].sq;
}
int k=v[r].sz;
for(auto h:v[r].ch){
if(h!=f){
k+=dfs3(h,r);
}
}
return k;
}
void dfs(int r,int f,int n){
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r,n);
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,int n){
for(auto h:v[r].ch){
if(h!=f){
dfs2(h,r,n);
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;
int n;
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);
}
for(int i=0;i<n;i++){
if(!dfn[i]){
tj(i,-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]){
assert(cv[h]+cc-1<s);
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){
int k=dfs3(i,i);
ans+=1ll*k*(k-1)*(k-2);
dfs(i,i,k);
dfs2(i,i,k);
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
21036 KB |
Output is correct |
| 2 |
Correct |
119 ms |
21052 KB |
Output is correct |
| 3 |
Correct |
105 ms |
28524 KB |
Output is correct |
| 4 |
Correct |
127 ms |
22940 KB |
Output is correct |
| 5 |
Correct |
92 ms |
21952 KB |
Output is correct |
| 6 |
Correct |
102 ms |
30616 KB |
Output is correct |
| 7 |
Correct |
100 ms |
26060 KB |
Output is correct |
| 8 |
Correct |
97 ms |
28752 KB |
Output is correct |
| 9 |
Correct |
125 ms |
24692 KB |
Output is correct |
| 10 |
Correct |
81 ms |
23532 KB |
Output is correct |
| 11 |
Correct |
74 ms |
17672 KB |
Output is correct |
| 12 |
Correct |
84 ms |
17660 KB |
Output is correct |
| 13 |
Correct |
79 ms |
16512 KB |
Output is correct |
| 14 |
Correct |
52 ms |
16300 KB |
Output is correct |
| 15 |
Correct |
43 ms |
13796 KB |
Output is correct |
| 16 |
Correct |
40 ms |
13696 KB |
Output is correct |
| 17 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 22 |
Correct |
4 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
47680 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
47676 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
