#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
ll n,m,u_i,v_i,dis[100005],low[100005],cnt,bcc,ans=0,num,sz[200005];
vector<ll> v[100005],g[200005];
stack<ll> stk;
void dfs(ll u,ll p)
{
dis[u]=low[u]=++cnt;
++num;
stk.push(u);
for(auto node:v[u])
{
if(node==p)continue;
if(dis[node]!=0)
{
low[u]=min(low[u],dis[node]);
}else
{
dfs(node,u);
low[u]=min(low[u],low[node]);
if(dis[u]<=low[node])
{
++bcc;
//printf("node=%d\n",node);
g[u].pb(n+bcc);
while(!g[n+bcc].size()||g[n+bcc].back()!=node)
{
g[n+bcc].pb(stk.top());
stk.pop();
}
}
}
}
}
void dfs2(ll u)
{
sz[u]=(u<=n);
for(auto node:g[u])
{
dfs2(node);
sz[u]+=sz[node];
if(u>n)ans-=(ll)g[u].size()*sz[node]*(sz[node]-1);
}
if(u>n)ans-=(ll)g[u].size()*(n-sz[u])*(n-sz[u]-1);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&u_i,&v_i);
v[u_i].pb(v_i);
v[v_i].pb(u_i);
}
for(int i=1;i<=n;i++)
{
if(dis[i]==0)
{
num=0;
dfs(i,0);
ans+=num*(num-1)*(num-2);
dfs2(i);
}
}
/*for(int i=1;i<=6;i++)
{
printf("i=%d\n",i);
for(auto node:g[i])
{
printf("%lld ",node);
}
printf("\n");
}
for(int i=1;i<=6;i++)
{
printf("%lld ",sz[i]);
}
printf("\n");*/
printf("%lld\n",ans);
}
Compilation message
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%lld%lld",&u_i,&v_i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
7356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
7356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
25140 KB |
Output is correct |
2 |
Correct |
68 ms |
25128 KB |
Output is correct |
3 |
Incorrect |
78 ms |
23152 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7492 KB |
Output is correct |
5 |
Correct |
6 ms |
7508 KB |
Output is correct |
6 |
Correct |
5 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7508 KB |
Output is correct |
8 |
Correct |
4 ms |
7492 KB |
Output is correct |
9 |
Correct |
4 ms |
7492 KB |
Output is correct |
10 |
Incorrect |
5 ms |
7380 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
20564 KB |
Output is correct |
2 |
Correct |
76 ms |
20432 KB |
Output is correct |
3 |
Correct |
79 ms |
20364 KB |
Output is correct |
4 |
Correct |
81 ms |
20444 KB |
Output is correct |
5 |
Correct |
77 ms |
20408 KB |
Output is correct |
6 |
Correct |
89 ms |
27956 KB |
Output is correct |
7 |
Correct |
109 ms |
25288 KB |
Output is correct |
8 |
Correct |
94 ms |
24004 KB |
Output is correct |
9 |
Correct |
83 ms |
22784 KB |
Output is correct |
10 |
Incorrect |
77 ms |
20340 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7492 KB |
Output is correct |
2 |
Correct |
5 ms |
7496 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
5 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
4 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7392 KB |
Output is correct |
11 |
Correct |
6 ms |
7448 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
4 ms |
7488 KB |
Output is correct |
14 |
Correct |
4 ms |
7508 KB |
Output is correct |
15 |
Correct |
4 ms |
7492 KB |
Output is correct |
16 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
20380 KB |
Output is correct |
2 |
Correct |
79 ms |
20552 KB |
Output is correct |
3 |
Correct |
90 ms |
20016 KB |
Output is correct |
4 |
Correct |
90 ms |
18892 KB |
Output is correct |
5 |
Correct |
74 ms |
17428 KB |
Output is correct |
6 |
Correct |
68 ms |
16964 KB |
Output is correct |
7 |
Correct |
70 ms |
16572 KB |
Output is correct |
8 |
Correct |
58 ms |
15964 KB |
Output is correct |
9 |
Correct |
65 ms |
15856 KB |
Output is correct |
10 |
Correct |
58 ms |
15680 KB |
Output is correct |
11 |
Correct |
61 ms |
15556 KB |
Output is correct |
12 |
Correct |
59 ms |
15416 KB |
Output is correct |
13 |
Correct |
61 ms |
15600 KB |
Output is correct |
14 |
Correct |
55 ms |
17892 KB |
Output is correct |
15 |
Correct |
100 ms |
24956 KB |
Output is correct |
16 |
Correct |
89 ms |
23284 KB |
Output is correct |
17 |
Correct |
90 ms |
23708 KB |
Output is correct |
18 |
Correct |
93 ms |
22256 KB |
Output is correct |
19 |
Incorrect |
80 ms |
18872 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
7356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
7356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |