#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e17*2;
const int N = 2e5 + 5;
vector<int> adj[N], low(N), in(N), vis(N), par(N), sz(N), sub(N);
int timer = 0;
vector<pair<int, int> > bridge;
void dfs(int node, int par){
vis[node] = 1;
in[node] = low[node] = timer++;
for(auto itr: adj[node]){
if(itr == par) continue;
if(vis[itr]){
low[node] = min(low[node], in[itr]);
}
else{
dfs(itr, node);
low[node] = min(low[node], low[itr]);
if(in[node] < low[itr]){
bridge.pb(mp(min(node, itr), max(node, itr)));
}
}
}
}
int find(int a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b){
par[find(b)] = find(a);
}
vector<int> adj2[N];
void dfs2(int node, int &cnt){
cnt++;
vis[node] = 1;
for(auto itr: adj2[node]){
if(!vis[itr]){
dfs2(itr, cnt);
merge(node, itr);
}
}
}
vector<int> adjb[N];
void subcalc(int node, int par){
for(auto itr: adjb[node]){
if(itr != par){
subcalc(itr, node);
sub[node] += sub[itr];
}
}
sub[node] += sz[node];
}
void dfs3(int node, int par, int total, int &ans){
vector<int> v;
for(auto itr: adjb[node]){
if(itr != par) v.pb(sub[itr]);
}
if(node != par) v.pb(total - sub[node]);
for(auto itr: v){
ans += sz[node] * itr * (total - sz[node] - itr);
}
for(auto itr: adjb[node]){
if(itr != par){
dfs3(itr, node, total, ans);
}
}
}
int32_t main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
cin>>n>>m;
vector<pair<int, int> > edge(m);
for(int i = 0; i < m; i++){
int u, v;
cin>>u>>v;
if(u > v) swap(u, v);
edge[i] = mp(u, v);
adj[u].pb(v);
adj[v].pb(u);
}
for(int i = 1; i <= n; i++){
dfs(i, i);
}
sort(bridge.begin(), bridge.end());
sort(edge.begin(), edge.end());
int bind = 0;
for(int i = 0; i < m; i++){
if(bind < bridge.size() && bridge[bind] == edge[i]){
bind++;
continue;
}
auto[u, v] = edge[i];
adj2[u].pb(v);
adj2[v].pb(u);
}
for(int i = 1; i <= n; i++){
vis[i] = 0;
par[i] = i;
sz[i] = 1;
}
int cnt = 0, ans = 0;
for(int i = 1; i <= n; i++){
if(!vis[i]){
dfs2(i, cnt);
sz[i] = cnt;
ans += cnt * (cnt - 1) * (cnt - 2); // 3 here, 0 other
ans += (cnt - 1) * (cnt - 1) * (n - cnt) * 2; // 2 here, 1 other
cnt = 0;
}
}
for(int i = 0; i < bridge.size(); i++){
auto[u, v] = bridge[i];
u = find(u), v = find(v);
adjb[u].pb(v);
adjb[v].pb(u);
}
for(int i = 1; i <= n; i++){
vis[i] = 0;
}
subcalc(find(1), find(1));
dfs3(find(1), find(1), n, ans);
cout<<ans<<endl;
return 0;
}
Compilation message
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:110:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | if(bind < bridge.size() && bridge[bind] == edge[i]){
| ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:135:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < bridge.size(); i++){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
43860 KB |
Output is correct |
| 2 |
Correct |
73 ms |
43860 KB |
Output is correct |
| 3 |
Incorrect |
66 ms |
39088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 3 |
Correct |
7 ms |
23852 KB |
Output is correct |
| 4 |
Correct |
7 ms |
24048 KB |
Output is correct |
| 5 |
Correct |
7 ms |
24156 KB |
Output is correct |
| 6 |
Correct |
7 ms |
24036 KB |
Output is correct |
| 7 |
Correct |
8 ms |
23900 KB |
Output is correct |
| 8 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 9 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 10 |
Incorrect |
7 ms |
23900 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
35784 KB |
Output is correct |
| 2 |
Correct |
88 ms |
35780 KB |
Output is correct |
| 3 |
Correct |
89 ms |
35660 KB |
Output is correct |
| 4 |
Correct |
85 ms |
35824 KB |
Output is correct |
| 5 |
Correct |
87 ms |
35652 KB |
Output is correct |
| 6 |
Correct |
101 ms |
42944 KB |
Output is correct |
| 7 |
Correct |
86 ms |
41156 KB |
Output is correct |
| 8 |
Correct |
88 ms |
39616 KB |
Output is correct |
| 9 |
Correct |
81 ms |
38336 KB |
Output is correct |
| 10 |
Incorrect |
74 ms |
35776 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
8 ms |
23896 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
23900 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
35776 KB |
Output is correct |
| 2 |
Correct |
85 ms |
35408 KB |
Output is correct |
| 3 |
Incorrect |
87 ms |
36036 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
