#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
int n, m;
pair<int, int> ed[200010];
vector<int> input[100010], link[100010], linkrev[100010], bcc[100010];
bool ch[100010];
int arr[100010], re, c, col[100010];
LL subtree[100010], dp[100010], dp2[100010], dp3[100010];
LL ans;
unordered_set<LL> us;
void give_dir(int num)
{
if(ch[num])return;
ch[num]=true;
for(int i=0; i<input[num].size(); i++){
if(!us.count((LL)num*200000+(LL)input[num][i])&&!us.count((LL)input[num][i]*200000+(LL)num)){
link[num].pb(input[num][i]);
linkrev[input[num][i]].pb(num);
us.insert((LL)num*200000+(LL)input[num][i]);
us.insert((LL)input[num][i]*200000+(LL)num);
//printf("%d -> %d\n", num, input[num][i]);
}
give_dir(input[num][i]);
}
}
void dfs1(int num)
{
if(ch[num])return;
ch[num]=true;
for(int i=0; i<link[num].size(); i++){
dfs1(link[num][i]);
}
arr[++re]=num;
}
void dfs2(int num, int color)
{
if(col[num])return;
col[num]=color;
for(int i=0; i<linkrev[num].size(); i++){
dfs2(linkrev[num][i], color);
}
}
void tree_dp(int num)
{
if(ch[num])return;
ch[num]=true;
dp[num]=subtree[num];
dp3[num]=(subtree[num]-1)*(subtree[num]-1);
if(bcc[num].size()==1&&ch[bcc[num][0]]){
ans+=subtree[num]*(subtree[num]-1)*(subtree[num]-2)/2;
return;
}
for(int i=0; i<bcc[num].size(); i++){
if(ch[bcc[num][i]])continue;
tree_dp(bcc[num][i]);
dp[num]+=dp[bcc[num][i]];
dp2[num]+=dp2[bcc[num][i]];
dp2[num]+=subtree[num]*dp[bcc[num][i]];
dp3[num]+=dp3[bcc[num][i]];
ans+=subtree[num]*(dp2[bcc[num][i]]+dp3[bcc[num][i]]);
ans+=subtree[num]*(subtree[num]-1)*(subtree[num]-2)/2;
ans+=dp[bcc[num][i]]*(subtree[num]-1)*(subtree[num]-1);
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int a, b;
scanf("%d %d", &a, &b);
input[a].pb(b);
input[b].pb(a);
ed[i].F=a;
ed[i].S=b;
}
give_dir(1);
memset(ch, 0, sizeof(ch));
for(int i=1; i<=n; i++){
if(!ch[i])dfs1(i);
}
for(int i=n; i>=1; i--){
if(!col[arr[i]])dfs2(arr[i], ++c);
subtree[col[arr[i]]]++;
}
for(int i=1; i<=m; i++){
if(col[ed[i].F]!=col[ed[i].S]){
bcc[col[ed[i].F]].pb(col[ed[i].S]);
bcc[col[ed[i].S]].pb(col[ed[i].F]);
}
}
for(int i=1; i<=c; i++){
sort(all(bcc[i]));
bcc[i].erase(unique(all(bcc[i])), bcc[i].end());
}
memset(ch, 0, sizeof(ch));
for(int i=1; i<=c; i++){
tree_dp(i);
}
ans*=2;
printf("%lld", ans);
}
Compilation message
count_triplets.cpp: In function 'void give_dir(int)':
count_triplets.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<input[num].size(); i++){
~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs1(int)':
count_triplets.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<link[num].size(); i++){
~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<linkrev[num].size(); i++){
~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void tree_dp(int)':
count_triplets.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<bcc[num].size(); i++){
~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
292 ms |
38220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
282 ms |
33768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
276 ms |
33764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
