#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_back
#define F first
#define S second
#define endl '\n'
// #define __debug
#ifdef __debug
#define IOS (void)0
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(min((int)1e9-1,a[__i])<<' ');de(endl);}
#else
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define de(...) (void)0
#define ar(...) (void)0
#endif
/***********************************default***********************************/
const int maxn=1e5+9;
int n,m,res=0,sum,sz[maxn];
VI G[maxn];
void dfs(int u,int f){
sz[u]=1;
++sum;
REP(i,0,G[u].size()){
int v=G[u][i];
if(v==f)continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
void calc(int u,int f){
REP(i,0,G[u].size()){
int v=G[u][i];
if(v==f)continue;
calc(v,u);
res+=sz[v]*(sum-sz[v]-1);
}
}
main(){
IOS;
cin>>n>>m;
REP(i,0,m){
int u,v;cin>>u>>v,--u,--v;
G[u].pb(v),G[v].pb(u);
}
MST(sz,-1);
REP(i,0,n)if(sz[i]<0){
sum=0;
dfs(i,-1);
calc(i,-1);
}
cout<<2*res<<endl;
}
Compilation message
count_triplets.cpp: In function 'void dfs(int_fast64_t, int_fast64_t)':
count_triplets.cpp:23:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
^
count_triplets.cpp:49:2: note: in expansion of macro 'REP'
REP(i,0,G[u].size()){
^~~
count_triplets.cpp: In function 'void calc(int_fast64_t, int_fast64_t)':
count_triplets.cpp:23:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
^
count_triplets.cpp:58:2: note: in expansion of macro 'REP'
REP(i,0,G[u].size()){
^~~
count_triplets.cpp: At global scope:
count_triplets.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1158 ms |
929772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1158 ms |
929772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
107460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
7288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1158 ms |
929772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1158 ms |
929772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
