#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
vector<int> G[N],E[N];
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
int cnt,disc[N],low[N],tid,n,csz[N];
bool in[N];
stack<int> s;
void Tarjan(int u)
{
disc[u]=low[u]=++tid;
in[u]=1;s.push(u);
for(int v:G[u])
{
if(!disc[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=disc[u])
{
++cnt;
AddEdge(u,cnt);
csz[cnt]++;
int h;
do
{
h=s.top();
s.pop();
in[h]=0;
AddEdge(h,cnt);
csz[cnt]++;
}while(h!=v);
}
}
else if(in[v]) low[u]=min(low[u],disc[v]);
}
}
ll ans;
int sz[N],dep[N],up[N];
void DFSSZ(int u, int p)
{
sz[u]=u<=n;
dep[u]=dep[p]+(u<=n);
up[u]=n;
for(int v:E[u]) if(v!=p) DFSSZ(v,u),sz[u]+=sz[v],up[u]-=sz[v];
}
int rt[N];
void Solve(int u, int p, int root)
{
for(int v:E[u]) if(v!=p) Solve(v,u,root);
ll all=(ll)sz[u]*(sz[u]-1);
int ch=0;
for(int v:E[u]) if(v!=p) all-=(ll)sz[v]*(sz[v]-1),ch+=csz[v]-1;
if(u<=n) ans+=(ll)(sz[root]-1)*dep[p]*2;
ans-=all*(dep[u]+dep[p]);
//printf("all:%lld\n",all);
if(u<=n)
{
if(p) ans-=(ll)sz[u]*(csz[p]-1)*2*2;
ans-=(ll)up[u]*ch*2*2;
//printf("u:%i ans:%lld sz:%i up:%i dep:%i ch:%i csz[p]:%i\n",u,ans,sz[u],up[u],dep[u],ch,csz[p]);
}
rt[u]=root;
//else printf("u:%i ans:%i\n",u,ans);
}
int main()
{
int m,u,v;
scanf("%i %i",&n,&m);
cnt=n;
for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
vector<int> root;
for(int i=1;i<=n;i++) if(!disc[i]) Tarjan(i),root.pb(i);
for(int i:root) DFSSZ(i,0),Solve(i,0,i);
for(int i=n+1;i<=cnt;i++) ans+=(ll)csz[i]*(csz[i]-1)*sz[rt[i]]*2-(ll)csz[i]*(csz[i]-1)*(csz[i]-2);
printf("%lld\n",ans);
return 0;
}
Compilation message
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:73:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
30092 KB |
Output is correct |
| 2 |
Correct |
116 ms |
30320 KB |
Output is correct |
| 3 |
Incorrect |
150 ms |
28140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
24080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
23672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
