This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Why am I so stupid? :c
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
typedef long long ll;
using namespace std;
struct edge {
int u, v;
edge() {
u = v = 0;
}
} e[200005];
int tin[100005], fup[100005];
vector <int> adj[100005];
vector <int> cp[100005];
bool bad[200005];
int col[100005];
bool u[200005];
int timer, sz;
int n, m;
ll ans;
void dfs(int v, int pr) {
tin[v] = fup[v] = ++timer;
u[v] = 1;
for (int id : adj[v]) {
int to;
if (v == e[id].u) {
to = e[id].v;
}
else {
to = e[id].u;
}
if (to == pr) {
continue;
}
if (u[to]) {
fup[v] = min(fup[v], tin[to]);
}
else {
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] > tin[v]) {
bad[id] = 1;
}
}
}
}
void dfs2(int v) {
cp[sz].pb(v);
u[v] = 1;
for (int to : adj[v]) {
if (u[to]) {
continue;
}
dfs2(to);
}
}
void calc(int v, int st, int mlt, int cur) {
if (st != v) {
int a = cp[st].size();
int b = cp[v].size();
ans += 1ll * (a - 1) * (b - 1) * (mlt + a - 1 + b - 1);
ans += 1ll * (b - 1) * (mlt + b - 1);
ans += 1ll * (a - 1) * (mlt + a - 1);
ans += 1ll * mlt;
}
u[v] = 1;
for (int id : adj[v]) {
bool good = 1;
int to, nxt;
if (col[e[id].v] == v) {
if (e[id].v == cur || cur == -1) {
good = 0;
}
nxt = e[id].u;
}
else {
if (e[id].u == cur || cur == -1) {
good = 0;
}
nxt = e[id].v;
}
to = col[nxt];
if (u[to]) {
continue;
}
calc(to, st, mlt + 1 + good * (cp[v].size() - 1), nxt);
}
}
ll f(ll x) {
return x * (x - 1) * (x - 2);
}
void solve() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &e[i].u, &e[i].v);
adj[e[i].u].pb(i);
adj[e[i].v].pb(i);
}
for (int i = 1; i <= n; ++i) {
if (u[i]) {
continue;
}
dfs(i, -1);
}
for (int i = 1; i <= n; ++i) {
adj[i].clear();
u[i] = 0;
}
for (int i = 1; i <= m; ++i) {
if (!bad[i]) {
adj[e[i].u].pb(e[i].v);
adj[e[i].v].pb(e[i].u);
}
}
for (int i = 1; i <= n; ++i) {
if (u[i]) {
continue;
}
++sz; dfs2(i);
for (int it : cp[sz]) {
col[it] = sz;
}
}
for (int i = 1; i <= n; ++i) {
adj[i].clear();
u[i] = 0;
}
for (int i = 1; i <= m; ++i) {
if (bad[i]) {
adj[col[e[i].v]].pb(i);
adj[col[e[i].u]].pb(i);
}
}
for (int i = 1; i <= sz; ++i) {
ans += f(cp[i].size());
for (int j = 1; j <= sz; ++j) {
u[j] = 0;
}
calc(i, i, -1, -1);
}
printf("%lld\n", ans);
}
int main() {
#ifdef BThero
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // BThero
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
Compilation message (stderr)
count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &e[i].u, &e[i].v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |