This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 2e5 + 5;
int n, m;
ll ans;
bool vs[SIZE];
int gn, sz[SIZE];
vector<int> adj[SIZE], gadj[SIZE];
ll P(int x, int y) {
if (y < 0 || y > x) return 0;
if (y == 2) return 1ll * x * (x - 1);
if (y == 3) return 1ll * x * (x - 1) * (x - 2);
}
struct VBCC { // need adj
int n, dfcnt = 0, bccnt = 0;
vector<int> dfn, low, st;
vector<vector<int>> bcc;
VBCC() {}
VBCC(int n) : n(n) {
dfn = low = vector<int>(n + 1, 0);
bcc = vector<vector<int>>(n + 1, vector<int>());
}
void tarjan(int pos, int fa) {
dfn[pos] = low[pos] = ++dfcnt;
st.emplace_back(pos);
for (int np : adj[pos]) {
if (np != fa) {
if (dfn[np] == 0) {
tarjan(np, pos);
low[pos] = min(low[pos], low[np]);
if (dfn[pos] <= low[np]) {
bccnt++;
while (1) {
int x = st.back();
bcc[x].emplace_back(bccnt);
st.pop_back();
if (x == np) {
break;
}
}
bcc[pos].emplace_back(bccnt);
}
} else {
low[pos] = min(low[pos], dfn[np]);
}
}
}
if (pos == fa) {
st.pop_back();
if (bcc[pos].size() == 0) {
bcc[pos].emplace_back(++bccnt);
}
}
}
void work() {
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
tarjan(i, i);
}
}
gn = bccnt;
FOR (i, 1, n) {
if (bcc[i].size() == 1) sz[bcc[i][0]]++;
else {
sz[++gn] = 1;
for (int x : bcc[i]) {
gadj[gn].pb(x);
gadj[x].pb(gn);
}
}
}
FOR (i, 1, gn) if (!vs[i]) {
int all = 0;
auto pre = [&](auto pre, int pos, int fa)->void {
all += sz[pos];
for (int np : gadj[pos]) if (np != fa) pre(pre, np, pos);
};
pre(pre, i, i);
auto dfs = [&](auto dfs, int pos, int fa)->int {
vs[pos] = 1;
vector<int> v;
int sum = sz[pos];
for (int np : gadj[pos]) if (np != fa) {
int w = dfs(dfs, np, pos);
sum += w;
v.pb(w);
}
v.pb(all - sum);
ans += P(sz[pos], 3);
if (pos > bccnt) {
for (int np : gadj[pos]) ans += P(sz[np], 2);
}
for (int x : v) {
ans += 2 * P(sz[pos], 2) * x;
ans += 1ll * sz[pos] * x * (all - sz[pos] - x);
}
return sum;
};
dfs(dfs, i, i);
}
}
} G;
void solve() {
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
G = VBCC(n);
G.work();
cout << ans << '\n';
}
int main() {
Waimai;
solve();
}
Compilation message (stderr)
count_triplets.cpp: In function 'long long int P(int, int)':
count_triplets.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
34 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |