#include <bits/stdc++.h>
using namespace std;
int n, m;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct node{
int depth = -1;
int low;
int parent;
bool vis = false;
bool isArti = false;
vi adj;
};
vector<unordered_set<int> > biconnected;
stack<int> s; ///this is only needed for biconnected components
///note: this will ignore single nodes with no edges
static node g[200005];
int rootChildren = 0;
void dfs(int u){
if(g[u].depth == -1) g[u].depth = g[g[u].parent].depth + 1;
g[u].low = g[u].depth;
g[u].vis = true;
for(int i = 0;i < g[u].adj.size();i++){
int v = g[u].adj[i];
if(!g[v].vis){
g[v].parent = u;
if(g[u].depth == 0) rootChildren++;
s.push(u); ///s traces the path of tree traversal
dfs(v);
g[u].low = min(g[u].low,g[v].low);
if(g[v].low >= g[u].depth){
g[u].isArti = true;
g[u].low = min(g[u].low,g[v].low);
unordered_set<int> newSet;
int nn;
biconnected.push_back(newSet); ///create new biconnected component
do{
assert(!s.empty());
nn = s.top();
s.pop();
biconnected.back().insert(nn);
}while(nn != u);
}
///if(g[v].low > g[u].depth{
///u,v is a bridge
///}
}
else if(v != g[u].parent){
g[u].low = min(g[u].low,g[v].low);
}
s.push(u);
}
}
struct node2{
long long sz;
long long dp = 0;
bool isArti = false;
bool vis = false;
int p = -1;
vi adj;
};
vector<node2> bct; ///block-cut tree
long long ans = 0ll;
long long dp(int u, int p){
bct[u].dp = bct[u].sz;
for(int j = 0;j < bct[u].adj.size();j++){
int v = bct[u].adj[j];
if(v != p)
bct[u].dp += dp(v,u);
}
return bct[u].dp;
}
void countWays(int u, long long total){
long long sz = bct[u].sz;
//if(bct[u].vis) return;
bct[u].vis = true;
if(!bct[u].isArti){
ans += sz * (sz - 1) * (sz + bct[u].adj.size() - 2);
ans += 2ll * sz * (sz + bct[u].adj.size() - 2) * (total - sz);
}
long long others = total - bct[u].dp;
for(int j = 0;j < bct[u].adj.size();j++){
int v = bct[u].adj[j];
if(!bct[v].vis){
countWays(v,total);
long long extra = 0ll;
if(!bct[u].isArti) extra = bct[u].adj.size()-2;
ans += 2ll * (bct[u].sz + extra) * bct[v].dp * others;
others += bct[v].dp;
}
}
}
int main()
{
//freopen("i.txt","r",stdin);
cin >> n >> m;
ii edges[m];
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b;
a--;
b--;
g[a].adj.push_back(b);
g[b].adj.push_back(a);
edges[i] = ii(a,b);
}
for(int i = 0;i < n;i++){
if(!g[i].vis){
rootChildren = 0;
g[i].depth = 0;
dfs(i);
if(rootChildren > 1) g[i].isArti = true;
else g[i].isArti = false; ///this line is needed
}
}
unordered_map<int,int> artis;
for(int i = 0;i < n;i++){
if(g[i].isArti){
artis[i] = bct.size();
node2 nn;
nn.sz = 1;
nn.isArti = true;
bct.push_back(nn);
}
}
vi components[n];
for(int i = 0;i < biconnected.size();i++){
node2 nn;
nn.isArti = false;
nn.sz = biconnected[i].size();
bct.push_back(nn);
for(int j : biconnected[i]){
components[j].push_back(i+artis.size());
}
}
for(int i = 0;i < n;i++){
if(g[i].isArti){
for(int j = 0;j < components[i].size();j++){
int v = components[i][j];
bct[v].sz--;
bct[v].adj.push_back(artis[i]);
bct[artis[i]].adj.push_back(v);
}
}
}
for(int i = 0;i < bct.size();i++){
if(!bct[i].vis) countWays(i,dp(i,-1));
}
/*
long long ans = 0ll;
for(int i = 0;i < bct.size();i++){
long long total = bct[bct[i].r].dp - bct[i].sz;
long long sz = bct[i].sz;
if(!bct[i].isArti){
ans += sz * (sz - 1) * (sz + bct[i].adj.size() - 2);
ans += 2ll * sz * (sz + bct[i].adj.size() - 2) * total;
}
long long others = bct[bct[i].r].dp - bct[i].dp;
for(int j = 0;j < bct[i].adj.size();j++){
int v = bct[i].adj[j];
if(v != bct[i].p){
long long extra = 0ll;
if(!bct[i].isArti) extra = bct[i].adj.size()-2;
ans += 2ll * (bct[i].sz + extra) * bct[v].dp * others;
others += bct[v].dp;
}
}
//if(!bct[i].isArti) ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].adj.size());
//cout << i << " " << ans << "\n";
}
*/
cout << ans;
}
/*
8 7
8 5
8 1
7 5
8 6
3 1
3 2
8 3
*/
/*
10 12
6 4
10 3
4 2
4 1
4 3
6 5
9 1
9 4
2 1
9 3
8 5
7 2
*/
Compilation message
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < g[u].adj.size();i++){
~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int dp(int, int)':
count_triplets.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[u].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void countWays(int, long long int)':
count_triplets.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[u].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:133:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < biconnected.size();i++){
~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:145:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < components[i].size();j++){
~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:157:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
10 ms |
8192 KB |
Output is correct |
4 |
Correct |
11 ms |
8192 KB |
Output is correct |
5 |
Correct |
11 ms |
8192 KB |
Output is correct |
6 |
Correct |
11 ms |
8192 KB |
Output is correct |
7 |
Correct |
12 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8192 KB |
Output is correct |
9 |
Correct |
10 ms |
8192 KB |
Output is correct |
10 |
Correct |
11 ms |
8192 KB |
Output is correct |
11 |
Correct |
10 ms |
8192 KB |
Output is correct |
12 |
Correct |
10 ms |
8192 KB |
Output is correct |
13 |
Correct |
10 ms |
8192 KB |
Output is correct |
14 |
Correct |
10 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
10 ms |
8192 KB |
Output is correct |
19 |
Correct |
11 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
9 ms |
8192 KB |
Output is correct |
22 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
10 ms |
8192 KB |
Output is correct |
4 |
Correct |
11 ms |
8192 KB |
Output is correct |
5 |
Correct |
11 ms |
8192 KB |
Output is correct |
6 |
Correct |
11 ms |
8192 KB |
Output is correct |
7 |
Correct |
12 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8192 KB |
Output is correct |
9 |
Correct |
10 ms |
8192 KB |
Output is correct |
10 |
Correct |
11 ms |
8192 KB |
Output is correct |
11 |
Correct |
10 ms |
8192 KB |
Output is correct |
12 |
Correct |
10 ms |
8192 KB |
Output is correct |
13 |
Correct |
10 ms |
8192 KB |
Output is correct |
14 |
Correct |
10 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
10 ms |
8192 KB |
Output is correct |
19 |
Correct |
11 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
9 ms |
8192 KB |
Output is correct |
22 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
34948 KB |
Output is correct |
2 |
Correct |
257 ms |
34996 KB |
Output is correct |
3 |
Correct |
380 ms |
42484 KB |
Output is correct |
4 |
Correct |
300 ms |
39080 KB |
Output is correct |
5 |
Correct |
308 ms |
36212 KB |
Output is correct |
6 |
Correct |
399 ms |
42588 KB |
Output is correct |
7 |
Correct |
421 ms |
42428 KB |
Output is correct |
8 |
Correct |
438 ms |
42752 KB |
Output is correct |
9 |
Correct |
410 ms |
41548 KB |
Output is correct |
10 |
Correct |
380 ms |
38736 KB |
Output is correct |
11 |
Correct |
213 ms |
33012 KB |
Output is correct |
12 |
Correct |
254 ms |
32832 KB |
Output is correct |
13 |
Correct |
251 ms |
32592 KB |
Output is correct |
14 |
Correct |
277 ms |
32064 KB |
Output is correct |
15 |
Correct |
183 ms |
26700 KB |
Output is correct |
16 |
Correct |
171 ms |
26440 KB |
Output is correct |
17 |
Correct |
17 ms |
10624 KB |
Output is correct |
18 |
Correct |
14 ms |
10624 KB |
Output is correct |
19 |
Correct |
12 ms |
10496 KB |
Output is correct |
20 |
Correct |
13 ms |
10624 KB |
Output is correct |
21 |
Correct |
14 ms |
10496 KB |
Output is correct |
22 |
Correct |
13 ms |
10496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
8576 KB |
Output is correct |
2 |
Correct |
12 ms |
8576 KB |
Output is correct |
3 |
Correct |
12 ms |
8496 KB |
Output is correct |
4 |
Correct |
13 ms |
8704 KB |
Output is correct |
5 |
Correct |
13 ms |
8576 KB |
Output is correct |
6 |
Correct |
11 ms |
8576 KB |
Output is correct |
7 |
Correct |
11 ms |
8696 KB |
Output is correct |
8 |
Correct |
12 ms |
8576 KB |
Output is correct |
9 |
Correct |
12 ms |
8704 KB |
Output is correct |
10 |
Correct |
14 ms |
8576 KB |
Output is correct |
11 |
Correct |
11 ms |
8576 KB |
Output is correct |
12 |
Correct |
12 ms |
8704 KB |
Output is correct |
13 |
Correct |
11 ms |
8576 KB |
Output is correct |
14 |
Correct |
11 ms |
8576 KB |
Output is correct |
15 |
Correct |
11 ms |
8448 KB |
Output is correct |
16 |
Correct |
9 ms |
8320 KB |
Output is correct |
17 |
Correct |
10 ms |
8448 KB |
Output is correct |
18 |
Correct |
10 ms |
8448 KB |
Output is correct |
19 |
Correct |
10 ms |
8476 KB |
Output is correct |
20 |
Correct |
10 ms |
8448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
47920 KB |
Output is correct |
2 |
Correct |
368 ms |
48104 KB |
Output is correct |
3 |
Correct |
362 ms |
48096 KB |
Output is correct |
4 |
Correct |
385 ms |
48308 KB |
Output is correct |
5 |
Correct |
372 ms |
48184 KB |
Output is correct |
6 |
Correct |
498 ms |
58676 KB |
Output is correct |
7 |
Correct |
464 ms |
53036 KB |
Output is correct |
8 |
Correct |
482 ms |
52420 KB |
Output is correct |
9 |
Correct |
472 ms |
50964 KB |
Output is correct |
10 |
Correct |
426 ms |
48336 KB |
Output is correct |
11 |
Correct |
394 ms |
48328 KB |
Output is correct |
12 |
Correct |
391 ms |
48284 KB |
Output is correct |
13 |
Correct |
385 ms |
48056 KB |
Output is correct |
14 |
Correct |
322 ms |
46392 KB |
Output is correct |
15 |
Correct |
289 ms |
40560 KB |
Output is correct |
16 |
Correct |
173 ms |
30148 KB |
Output is correct |
17 |
Correct |
244 ms |
41932 KB |
Output is correct |
18 |
Correct |
248 ms |
41776 KB |
Output is correct |
19 |
Correct |
232 ms |
42252 KB |
Output is correct |
20 |
Correct |
244 ms |
42040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8576 KB |
Output is correct |
2 |
Correct |
13 ms |
8576 KB |
Output is correct |
3 |
Correct |
12 ms |
8576 KB |
Output is correct |
4 |
Correct |
13 ms |
8576 KB |
Output is correct |
5 |
Correct |
11 ms |
8320 KB |
Output is correct |
6 |
Correct |
11 ms |
8320 KB |
Output is correct |
7 |
Correct |
12 ms |
8448 KB |
Output is correct |
8 |
Correct |
11 ms |
8320 KB |
Output is correct |
9 |
Correct |
13 ms |
8320 KB |
Output is correct |
10 |
Correct |
12 ms |
8320 KB |
Output is correct |
11 |
Correct |
13 ms |
8320 KB |
Output is correct |
12 |
Correct |
11 ms |
8576 KB |
Output is correct |
13 |
Correct |
12 ms |
8484 KB |
Output is correct |
14 |
Correct |
14 ms |
8576 KB |
Output is correct |
15 |
Correct |
14 ms |
8576 KB |
Output is correct |
16 |
Correct |
14 ms |
8448 KB |
Output is correct |
17 |
Correct |
13 ms |
8448 KB |
Output is correct |
18 |
Correct |
13 ms |
8448 KB |
Output is correct |
19 |
Correct |
11 ms |
8468 KB |
Output is correct |
20 |
Correct |
11 ms |
8320 KB |
Output is correct |
21 |
Correct |
12 ms |
8576 KB |
Output is correct |
22 |
Correct |
11 ms |
8576 KB |
Output is correct |
23 |
Correct |
11 ms |
8448 KB |
Output is correct |
24 |
Correct |
12 ms |
8448 KB |
Output is correct |
25 |
Correct |
10 ms |
8320 KB |
Output is correct |
26 |
Correct |
12 ms |
8192 KB |
Output is correct |
27 |
Correct |
10 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
47980 KB |
Output is correct |
2 |
Correct |
401 ms |
48288 KB |
Output is correct |
3 |
Correct |
418 ms |
46704 KB |
Output is correct |
4 |
Correct |
388 ms |
38860 KB |
Output is correct |
5 |
Correct |
311 ms |
32224 KB |
Output is correct |
6 |
Correct |
306 ms |
29196 KB |
Output is correct |
7 |
Correct |
309 ms |
27672 KB |
Output is correct |
8 |
Correct |
227 ms |
25804 KB |
Output is correct |
9 |
Correct |
243 ms |
24980 KB |
Output is correct |
10 |
Correct |
251 ms |
24580 KB |
Output is correct |
11 |
Correct |
228 ms |
23348 KB |
Output is correct |
12 |
Correct |
235 ms |
22456 KB |
Output is correct |
13 |
Correct |
196 ms |
22220 KB |
Output is correct |
14 |
Correct |
275 ms |
23952 KB |
Output is correct |
15 |
Correct |
526 ms |
50744 KB |
Output is correct |
16 |
Correct |
410 ms |
48564 KB |
Output is correct |
17 |
Correct |
464 ms |
46496 KB |
Output is correct |
18 |
Correct |
394 ms |
44368 KB |
Output is correct |
19 |
Correct |
362 ms |
38680 KB |
Output is correct |
20 |
Correct |
398 ms |
38772 KB |
Output is correct |
21 |
Correct |
391 ms |
38776 KB |
Output is correct |
22 |
Correct |
301 ms |
35272 KB |
Output is correct |
23 |
Correct |
244 ms |
30932 KB |
Output is correct |
24 |
Correct |
317 ms |
42556 KB |
Output is correct |
25 |
Correct |
385 ms |
42984 KB |
Output is correct |
26 |
Correct |
318 ms |
39572 KB |
Output is correct |
27 |
Correct |
375 ms |
39624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
10 ms |
8192 KB |
Output is correct |
4 |
Correct |
11 ms |
8192 KB |
Output is correct |
5 |
Correct |
11 ms |
8192 KB |
Output is correct |
6 |
Correct |
11 ms |
8192 KB |
Output is correct |
7 |
Correct |
12 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8192 KB |
Output is correct |
9 |
Correct |
10 ms |
8192 KB |
Output is correct |
10 |
Correct |
11 ms |
8192 KB |
Output is correct |
11 |
Correct |
10 ms |
8192 KB |
Output is correct |
12 |
Correct |
10 ms |
8192 KB |
Output is correct |
13 |
Correct |
10 ms |
8192 KB |
Output is correct |
14 |
Correct |
10 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
10 ms |
8192 KB |
Output is correct |
19 |
Correct |
11 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
9 ms |
8192 KB |
Output is correct |
22 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
10 ms |
8192 KB |
Output is correct |
4 |
Correct |
11 ms |
8192 KB |
Output is correct |
5 |
Correct |
11 ms |
8192 KB |
Output is correct |
6 |
Correct |
11 ms |
8192 KB |
Output is correct |
7 |
Correct |
12 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8192 KB |
Output is correct |
9 |
Correct |
10 ms |
8192 KB |
Output is correct |
10 |
Correct |
11 ms |
8192 KB |
Output is correct |
11 |
Correct |
10 ms |
8192 KB |
Output is correct |
12 |
Correct |
10 ms |
8192 KB |
Output is correct |
13 |
Correct |
10 ms |
8192 KB |
Output is correct |
14 |
Correct |
10 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
10 ms |
8192 KB |
Output is correct |
19 |
Correct |
11 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
9 ms |
8192 KB |
Output is correct |
22 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |