#include <bits/stdc++.h>
#define DIMN 100005
#define DIMM 200005
using namespace std;
long long low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[DIMN];
long long cnt[DIMN];
stack <long long> st;
vector <long long> v[DIMN] , w[2 * DIMN];
set <long long> sol[DIMN];
long long x , n , val;
void dfs_bic (long long nod,long long tt){
long long i,vecin;
low[nod]=lvl[nod];
st.push(nod);
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin==tt)
continue;
if (lvl[vecin]==0){
lvl[vecin]=1+lvl[nod];
dfs_bic(vecin,nod);
low[nod]=min(low[nod],low[vecin]);
if (low[vecin]>=lvl[nod]){ /// nod e un nod critic
bicnx++;
do{
x=st.top();
taken[x]++;
st.pop();
sol[bicnx].insert(x);
}
while (x!=vecin);
sol[bicnx].insert(nod);
taken[nod]++;
/// am scos din stiva muchiile care sunt in subarborele nod->vecin
}
}
else low[nod]=min(low[nod],lvl[vecin]);
}
}
void dfs (long long nod){
long long sum , i , vecin , tata=0 , coupled;
//prlong longf ("%lld ",nod);
f[nod] = 1;
sum = 0;
if (nod > n){ /// nod
under[nod] = 1;
two[nod] = 0;
}
else { /// componenta
under[nod] = sol[bicnx - nod + 1].size();
two[nod] = 0;
}
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (!f[vecin]){
dfs(vecin);
under[nod] += under[vecin] - 1;
sum += under[vecin];
//if (nod > n)
two[nod] += two[vecin];
}
else tata = vecin;
}
if (nod <= n){ /// componenta
x = sol[bicnx - nod + 1].size();
if (x == 2){
two[nod]++;
}
else {
two[nod] += x * (x - 1) / 2;
two[nod] += (x - w[nod].size() + (tata != 0)) * (x - w[nod].size() - 1 + (tata != 0)) / 2;
/// alegi 2 noduri ne-critice in orice ordine
/// pe de alta pt, pot sa iau un nod din comp de aici si un nod
/// din una de jos
}
two[nod] += (x - 1) * (under[nod] - x);
}
//if (nod == 1)
// printf ("a");
if (nod > n){ /// nod
sum = under[nod];
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin != tata){
/// iau un nod din subarb vecin, trec prin nodul critic nod
/// si ma duc pe altundv
val = val + (under[vecin] - 1) * (sum - under[vecin]);
coupled = 0;
if (under[vecin] - 1 >= 2){
/// iei doua din vecin si unul de altundeva, fara sa iei nodul critic
coupled = (under[vecin] - 1);
if (sol[bicnx - vecin + 1].size() > 2){
coupled += sol[bicnx - vecin + 1].size() - 1;
}
val = val + 2 * (two[vecin] - coupled) * (sum - under[vecin]);
}
cnt[nod] += coupled;
//val = val + two[vecin] - under[vecin] + 1;
}
}
}
else { /// componenta
if (sol[bicnx - nod + 1].size() >= 3){
x = sol[bicnx - nod + 1].size();
val = val + x * (x - 1) * (x - 2);
/// iei 3 din aceeasi comp, CU noduri critice!!!
}
x = sol[bicnx - nod + 1].size();
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin != tata){
/// din subarborele lui vecin iau 2, din alt subarbore iau unul
val = val + 2 * (sum - under[vecin]) * two[vecin];
/// iau 1 din nodul curent si doua de sub
coupled = cnt[vecin];
/*if (sol[bicnx - vecin + 1].size() > 2){
coupled += sol[bicnx - vecin + 1].size() - 1;
}*/
val = val + 2 * (x - 1) * ( two[vecin] - coupled );
if (x >= 2){
val = val + 2 * (x - 1) * (x - 2) * (under[vecin] - 1);
val = val + 2 * (x - 1) * (under[vecin] - 1);
}
}
}
}
// printf ("%lld %lld\n" , nod , val);
}
int main()
{
FILE *fin=stdin;
FILE *fout=stdout;
long long m , i , x , y , nod;
fscanf (fin,"%lld%lld",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%lld%lld",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for (i = 1 ; i <= n ; i++){
if (!lvl[i]){
lvl[i] = 1;
dfs_bic (i , 0);
}
}
/// taken[nod] > 1 => nod critic
for (i = 1 ; i <= bicnx ; i++){
for (set <long long> :: iterator it = sol[i].begin() ; it != sol[i].end() ; it++){
nod = *it;
//printf ("%lld " , nod);
nod += n;
if (taken[nod - n] > 1){
w[nod].push_back(bicnx - i + 1);
//printf ("%lld %lld\n" , nod , bicnx - i + 1);
w[bicnx - i + 1].push_back(nod);
}
}
//printf ("\n");
}
/// w e arborele componentelor biconexe
/// sau sunt mai multi arbori daca graful nu era conex
for (i = 1 ; i <= bicnx ; i++){
if (!f[i]){
dfs (i);
}
}
//dfs(1);
fprintf (fout,"%lld",val);
return 0;
}
Compilation message
count_triplets.cpp: In function 'void dfs_bic(long long int, long long int)':
count_triplets.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int)':
count_triplets.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp:111:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp:156:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:195:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld",&n,&m);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:197:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12160 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12160 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
125 ms |
29816 KB |
Output is correct |
| 2 |
Correct |
133 ms |
29792 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
33272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
12416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
138 ms |
36472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
12416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
156 ms |
36472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12160 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
14 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
12 ms |
12160 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
