#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;
};
vector<unordered_set<int> > biconnected;
stack<int> s; ///this is only needed for biconnected components
///note: this will ignore single nodes with no edges
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++;
s.push(u); ///s traces the path of tree traversal
dfs(v);
g[u].low = min(g[u].low,g[v].low);
if(g[v].low >= g[u].depth){
g[u].isArti = true;
g[u].low = min(g[u].low,g[v].low);
unordered_set<int> newSet;
int nn;
biconnected.push_back(newSet); ///create new biconnected component
do{
assert(!s.empty());
nn = s.top();
s.pop();
biconnected.back().insert(nn);
}while(nn != u);
}
///if(g[v].low > g[u].depth{
///u,v is a bridge
///}
}
else if(v != g[u].parent){
g[u].low = min(g[u].low,g[v].low);
}
s.push(u);
}
}
struct node2{
long long sz;
long long dp = 0;
bool isArti = false;
bool vis = false;
int r;
int p = -1;
vi adj;
};
vector<node2> bct; ///block-cut tree
long long root = -1;
void dp(int u){
if(bct[u].vis) return;
bct[u].vis = true;
bct[u].dp = bct[u].sz;
bct[u].r = root;
for(int i = 0;i < bct[u].adj.size();i++){
int v = bct[u].adj[i];
if(bct[v].vis) continue;
bct[v].p = u;
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
}
}
unordered_map<int,int> artis;
for(int i = 0;i < n;i++){
if(g[i].isArti){
artis[i] = bct.size();
node2 nn;
nn.sz = 1;
nn.isArti = true;
bct.push_back(nn);
}
}
for(int i = 0;i < biconnected.size();i++){
node2 nn;
nn.sz = biconnected[i].size();
nn.isArti = false;
for(unordered_set<int>::iterator it = biconnected[i].begin();it != biconnected[i].end();it++){
//cout << *it << " ";
if(artis.find(*it) != artis.end()){
nn.adj.push_back(artis[*it]);
bct[artis[*it]].adj.push_back(bct.size());
nn.sz--;
}
}
bct.push_back(nn);
//cout << "\n";
}
for(int i = 0;i < bct.size();i++){
root = i;
dp(i);
}
set<long long> checl;
for(int i = 0;i < bct.size();i++){
//cout << i << " " << bct[i].sz << " " << bct[i].dp << " " << bct[i].isArti << "| ";
for(int j = 0;j < bct[i].adj.size();j++){
//cout << bct[i].adj[j] << " ";
long long q = i * 1000000000ll + j;
if(checl.find(q) != checl.end()) assert(false);
else checl.insert(q);
}
//cout << "\n";
}
long long ans = 0ll;
for(int i = 0;i < bct.size();i++){
vector<long long> branches;
vector<long long> branchStart;
long long total = 0ll;
for(int j = 0;j < bct[i].adj.size();j++){
if(bct[i].adj[j] != bct[i].p){
branches.push_back(bct[bct[i].adj[j]].dp);
branchStart.push_back(bct[bct[i].adj[j]].sz);
}
}
if(bct[i].p >= 0){
branches.push_back(bct[bct[i].r].dp - bct[i].dp);
branchStart.push_back(bct[bct[i].p].sz);
}
for(int j = 0;j < branches.size();j++) total += branches[j];
/*
long long extra = 0, extra2 = 0;
if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
if(!bct[i].isArti) extra2 = max(0ll,(long long)(bct[i].adj.size())-1);
for(int j = 0;j < branches.size();j++){
//cout << i << " " << branches[j] << "\n";
///branch1 to self or neighbor articulation point to branch2
ans += branches[j] * (total - branches[j]) * (bct[i].sz + extra);
///branch to self to self or self to self to branch
ans += 2 * (bct[i].sz) * (bct[i].sz + extra2 - 1) * branches[j];
///self to arti to another branch
//if(!bct[i].isArti){
// ans += 2ll * (bct[i].sz) * branches[j] * (bct[i].adj.size() - 1);
//}
if(bct[i].isArti){
///direct branch to self to same branch(not reverse) or its reverse
ans += 2ll * bct[i].sz * branchStart[j] * (branches[j] - branchStart[j]);
///direct branch to self to direct or its reverse
ans += bct[i].sz * (branchStart[j]) * (branchStart[j] - 1);
}
}
///self to self to self
ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].sz - 2);
*/
long long sz = bct[i].sz;
if(!bct[i].isArti){
ans += sz * (sz - 1) * (sz + bct[i].adj.size() - 2);
ans += 2ll * sz * (sz + bct[i].adj.size() - 2) * total;
}
long long others = bct[bct[i].r].dp - bct[i].dp;
for(int j = 0;j < bct[i].adj.size();j++){
int v = bct[i].adj[j];
if(v != bct[i].p){
long long extra = bct[i].adj.size()-2;
if(!bct[i].isArti) extra = bct[i].adj.size()-2;
ans += 2ll * (bct[i].sz + extra) * bct[v].dp * others;
others += bct[v].dp;
}
}
//if(!bct[i].isArti) ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].adj.size());
//cout << i << " " << ans << "\n";
}
cout << ans;
}
Compilation message
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:25: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:74: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:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < biconnected.size();i++){
~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:133:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
count_triplets.cpp:139:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
count_triplets.cpp:141:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:151:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < bct.size();i++){
~~^~~~~~~~~~~~
count_triplets.cpp:155:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:165: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:203:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j < bct[i].adj.size();j++){
~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
8 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 |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
8 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 |
223 ms |
32324 KB |
Output is correct |
| 2 |
Correct |
227 ms |
32324 KB |
Output is correct |
| 3 |
Correct |
432 ms |
49516 KB |
Output is correct |
| 4 |
Correct |
410 ms |
40852 KB |
Output is correct |
| 5 |
Correct |
365 ms |
38764 KB |
Output is correct |
| 6 |
Correct |
462 ms |
50296 KB |
Output is correct |
| 7 |
Correct |
452 ms |
50140 KB |
Output is correct |
| 8 |
Correct |
515 ms |
51772 KB |
Output is correct |
| 9 |
Correct |
599 ms |
48732 KB |
Output is correct |
| 10 |
Correct |
497 ms |
44956 KB |
Output is correct |
| 11 |
Correct |
336 ms |
32508 KB |
Output is correct |
| 12 |
Correct |
347 ms |
32948 KB |
Output is correct |
| 13 |
Correct |
229 ms |
30788 KB |
Output is correct |
| 14 |
Correct |
216 ms |
30404 KB |
Output is correct |
| 15 |
Correct |
144 ms |
24336 KB |
Output is correct |
| 16 |
Correct |
144 ms |
23876 KB |
Output is correct |
| 17 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 18 |
Correct |
12 ms |
8320 KB |
Output is correct |
| 19 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 20 |
Correct |
11 ms |
8192 KB |
Output is correct |
| 21 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 22 |
Correct |
9 ms |
8192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
8704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
576 ms |
56264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
610 ms |
56352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
8 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 |
10 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8192 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
8192 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
