#include <bits/stdc++.h>
using namespace std;
int n, m;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct node{
int depth = -1;
int low;
int parent;
bool vis = false;
bool isArti = false;
vi adj;
};
static node g[200005];
int rootChildren = 0;
void dfs(int u){
if(g[u].depth == -1) g[u].depth = g[g[u].parent].depth + 1;
g[u].low = g[u].depth;
g[u].vis = true;
for(int i = 0;i < g[u].adj.size();i++){
int v = g[u].adj[i];
if(!g[v].vis){
g[v].parent = u;
if(g[u].depth == 0) rootChildren++;
dfs(v);
if(g[v].low >= g[u].depth){
g[u].isArti = true;
}
///if(g[v].low > g[u].depth{
///u,v is a bridge
///}
g[u].low = min(g[u].low,g[v].low);
}
else if(v != g[u].parent){
g[u].low = min(g[u].low,g[v].low);
}
}
}
class UFDS {
typedef vector<int> vi;
public:
vi p, rak, setSize;
int numSets;
void create(int n){
setSize.assign(n, 1);
numSets = n;
rak.assign(n, 0);
p.assign(n, 0);
for(int i =0;i < n;i++){
p[i] = i;
}
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
void unionSet(int i, int j){
if(isSameSet(i,j))
return;
numSets--;
int x = findSet(i);
int y = findSet(j);
if(rak[x] > rak[y]) {
p[y] = x; setSize[x] += setSize[y];
}
else {
p[x] = y; setSize[y] += setSize[x];
if(rak[x] == rak[y]) rak[y]++;
}
}
};
struct node2{
long long s;
long long dp = 0;
bool isArti = false;
bool vis = false;
int r;
vi adj;
};
vector<node2> bct; ///block-cut tree
long long root;
void dp(int u){
if(bct[u].vis) return;
bct[u].vis = true;
bct[u].dp = bct[u].s;
for(int i = 0;i < bct[u].adj.size();i++){
int v = bct[u].adj[i];
if(bct[v].vis) continue;
dp(v);
bct[u].dp += bct[v].dp;
}
}
int main()
{
//freopen("i.txt","r",stdin);
cin >> n >> m;
ii edges[m];
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b;
a--;
b--;
g[a].adj.push_back(b);
g[b].adj.push_back(a);
edges[i] = ii(a,b);
}
for(int i = 0;i < n;i++){
if(!g[i].vis){
rootChildren = 0;
g[i].depth = 0;
dfs(i);
if(rootChildren > 1) g[i].isArti = true;
else g[i].isArti = false; ///this line is needed
}
}
UFDS uf;
uf.create(n);
unordered_map<int,int> artis;
for(int i = 0;i < n;i++){
if(g[i].isArti){
node2 nn;
nn.s = 1;
nn.isArti = true;
artis[i] = bct.size();
bct.push_back(nn);
}
}
for(int i = 0;i < m;i++){
int a = edges[i].first;
int b = edges[i].second;
if(!g[a].isArti || !g[b].isArti){
uf.unionSet(a,b);
}
}
for(int i = 0;i < n;i++) g[i].vis = false;
queue<int> bfs;
for(int i = 0;i < n;i++){
if(g[i].vis || g[i].isArti) continue;
node2 nn;
nn.s = 0;
nn.isArti = false;
int x = bct.size();
bfs.push(i);
unordered_set<int> pushedStuff;
while(!bfs.empty()){
int u = bfs.front();
bfs.pop();
if(g[u].isArti){
int y = artis[u];
pushedStuff.insert(y);
continue;
}
if(g[u].vis) continue;
g[u].vis = true;
nn.s++;
for(int j = 0;j < g[u].adj.size();j++){
int v = g[u].adj[j];
bfs.push(v);
}
}
for(int y : pushedStuff){
nn.adj.push_back(y);
bct[y].adj.push_back(x);
}
bct.push_back(nn);
}
for(int i = 0;i < m;i++){
int a = edges[i].first;
int b = edges[i].second;
if(g[a].isArti && g[b].isArti && !uf.isSameSet(a,b)){
int x = artis[a];
int y = artis[b];
bct[x].adj.push_back(y);
bct[y].adj.push_back(x);
}
}
for(int i = 0;i < bct.size();i++){
root = i;
dp(i);
}
/*
for(int i = 0;i < bct.size();i++){
cout << bct[i].s << ", " << bct[i].dp << "| ";
for(int j = 0;j < bct[i].adj.size();j++){
cout << bct[i].adj[j] << " ";
}
cout << "\n";
}
*/
long long ans = 0ll;
for(int i = 0;i < bct.size();i++){
vector<long long> branches;
long long total = 0ll;
for(int j = 0;j < bct[i].adj.size();j++){
if(bct[bct[i].adj[j]].dp <= bct[i].dp){
branches.push_back(bct[bct[i].adj[j]].dp);
}
}
branches.push_back(bct[bct[i].r].dp - bct[i].dp);
for(int j = 0;j < branches.size();j++) total += branches[j];
for(int j = 0;j < branches.size();j++){
//cout << total << " " << branches[j] << " " << bct[i].s << "\n";
///branch1->self->branch2
ans += branches[j] * bct[i].s * (total - branches[j]);
///self->self->branch or branch->self->self
ans += 2ll * (bct[i].s) * (bct[i].s - 1ll) * branches[j];
}
if(!bct[i].isArti){
long long neighbours = bct[i].adj.size();
ans += (bct[i].s) * (bct[i].s - 1ll) * neighbours;
ans += (bct[i].s) * (bct[i].s - 1ll) * (bct[i].s - 2ll);
}
}
cout << ans;
}
Compilation message
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < g[u].adj.size();i++){
~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dp(int)':
count_triplets.cpp:104:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct[u].adj.size();i++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:178:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < g[u].adj.size();j++){
~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:199:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
count_triplets.cpp:215:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
count_triplets.cpp:218:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:224:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < branches.size();j++) total += branches[j];
~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:227:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < branches.size();j++){
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8092 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8092 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
17904 KB |
Output is correct |
| 2 |
Correct |
202 ms |
17940 KB |
Output is correct |
| 3 |
Incorrect |
268 ms |
21712 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
14 ms |
8320 KB |
Output is correct |
| 5 |
Correct |
14 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 7 |
Correct |
13 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
10 ms |
8320 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
8320 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
354 ms |
23416 KB |
Output is correct |
| 2 |
Correct |
343 ms |
23436 KB |
Output is correct |
| 3 |
Correct |
346 ms |
23456 KB |
Output is correct |
| 4 |
Correct |
342 ms |
23472 KB |
Output is correct |
| 5 |
Correct |
283 ms |
23324 KB |
Output is correct |
| 6 |
Correct |
347 ms |
27548 KB |
Output is correct |
| 7 |
Correct |
399 ms |
26012 KB |
Output is correct |
| 8 |
Correct |
345 ms |
25500 KB |
Output is correct |
| 9 |
Correct |
332 ms |
25236 KB |
Output is correct |
| 10 |
Incorrect |
392 ms |
23436 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
8240 KB |
Output is correct |
| 2 |
Correct |
13 ms |
8320 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
8320 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
23604 KB |
Output is correct |
| 2 |
Correct |
328 ms |
23944 KB |
Output is correct |
| 3 |
Incorrect |
426 ms |
23196 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8092 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8092 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8192 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
