#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int MAXN = (int)1e5 + 5;
vector <int> g[MAXN];
vector <int> G[MAXN]; // кактусовый граф
int pr[MAXN];
bool used[MAXN];
bool black[MAXN];
vector <int> cycle[MAXN];
int ind[MAXN], cur_ind;
pii joop(int x, int y) {
if (x > y) {
swap(x, y);
}
return {x, y};
}
void precalc(int v, int par) {
pr[v] = par;
used[v] = 1;
for (int to : g[v]) {
if (to == par) {
continue;
}
if (used[to] && !black[to]) {
cur_ind++;
int fn = v;
while (fn != to) {
cycle[cur_ind].pb(fn);
fn = pr[fn];
}
cycle[cur_ind].pb(fn);
for (int el : cycle[cur_ind]) {
black[el] = 1;
ind[el] = cur_ind;
}
} else if (!used[to]) {
precalc(to, v);
}
}
}
int ans = 0;
int sub[MAXN];
int n, m;
void calc_sub(int v, int par) {
sub[v] = szof(cycle[ind[v]]);
for (int to : G[v]) {
if (to == par) {
continue;
}
calc_sub(to, v);
sub[v] += sub[to];
}
}
int root; // корень сжатого дерева
void calc_ans(int v, int par) {
int cur_add = 0;
auto calc_other = [&]() {
vector <int> vec;
for (int to : G[v]) {
if (to == par) {
continue;
}
vec.pb(sub[to]);
}
if (v != root) {
vec.pb(sub[root] - sub[v]);
}
int sum = 0;
int before = 0;
for (int el : vec) {
sum += before * el;
before += el;
}
return sum * 2;
};
if (!black[v]) {
ans += calc_other();
cur_add += calc_other();
} else {
auto calc_my = [&](int vrt) {
int my = 0;
for (int to : g[vrt]) {
if (ind[vrt] != ind[to]) {
int need = cycle[ind[to]][0];
if (need == par) {
my += n - sub[v];
} else {
my += sub[need];
}
}
}
return my;
};
auto have = [&](int v) {
bool flag = (szof(g[v]) > 2);
return flag;
};
// 1 in cycle
{
int kek = 0;
vector <int> vec;
for (int vrt : cycle[ind[v]]) {
if (have(vrt)) {
vec.pb(calc_my(vrt));
}
}
int before = 0;
for (int el : vec) {
kek += el * before;
before += el;
}
kek *= 2;
int between = calc_other();
for (int c : cycle[ind[v]]) {
if (have(c)) {
ans += between;
cur_add += between;
} else {
ans += kek;
cur_add += kek;
}
}
}
// 2 in cycle
{
int other = n - szof(cycle[ind[v]]);
int cycle_size = szof(cycle[ind[v]]);
for (int c : cycle[ind[v]]) {
if (have(c)) {
int my = calc_my(c);
ans += my * (cycle_size - 1) * 2;
cur_add += my * (cycle_size - 1) * 2;
} else {
int nw = 0;
for (int f : cycle[ind[v]]) {
if (c != f) {
ans += (other - calc_my(f)) * 2;
cur_add += (other - calc_my(f)) * 2;
nw += (other - calc_my(f)) * 2;
}
}
}
}
}
// 3 in cycle
{
int siz = szof(cycle[ind[v]]);
ans += siz * (siz - 1) * (siz - 2);
cur_add += siz * (siz - 1) * (siz - 2);
}
}
for (int to : G[v]) {
if (to == par) {
continue;
}
calc_ans(to, v);
}
}
signed main() {
fastInp;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
precalc(1, -1);
for (int i = 1; i <= n; i++) {
if (!black[i]) {
ind[i] = ++cur_ind;
cycle[ind[i]].pb(i);
}
}
set <pii> st;
for (int i = 1; i <= n; i++) {
for (int to : g[i]) {
if (ind[i] != ind[to]) {
st.insert(joop(ind[i], ind[to]));
}
}
}
for (auto el : st) {
int x = cycle[el.fr][0];
int y = cycle[el.sc][0];
G[x].pb(y);
G[y].pb(x);
}
root = cycle[1][0];
calc_sub(root, -1);
calc_ans(root, -1);
cout << ans << endl;
}
/*
10 11
1 2
2 3
2 4
4 3
1 5
5 6
6 9
6 10
5 7
7 8
5 8
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1036 ms |
21496 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
7508 KB |
Output is correct |
2 |
Correct |
6 ms |
7508 KB |
Output is correct |
3 |
Correct |
6 ms |
7500 KB |
Output is correct |
4 |
Correct |
6 ms |
7628 KB |
Output is correct |
5 |
Correct |
6 ms |
7628 KB |
Output is correct |
6 |
Correct |
6 ms |
7628 KB |
Output is correct |
7 |
Correct |
6 ms |
7636 KB |
Output is correct |
8 |
Correct |
6 ms |
7500 KB |
Output is correct |
9 |
Correct |
6 ms |
7500 KB |
Output is correct |
10 |
Incorrect |
6 ms |
7508 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
204 ms |
23148 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7500 KB |
Output is correct |
2 |
Correct |
6 ms |
7504 KB |
Output is correct |
3 |
Incorrect |
6 ms |
7500 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
212 ms |
23092 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |