#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxn = 1e5 + 20;
vector<int> adj[maxn];
vector<int> ch_color[maxn];
vector<int> comp;
int color[maxn];
int sz_color[maxn];
bool can[55][55][55];
bool bad[maxn];
bool flag[maxn];
int par[maxn];
int depth[maxn];
int high[maxn];
int sz[maxn];
int node_cnt = 0;
int edge_cnt = 0;
int n, m;
void dfs1(int x, int a, int b) {
can[x][a][b] = true;
for (auto c: adj[b]) {
if (c != x && !can[x][a][c]) {
dfs1(x, a, c);
}
}
}
void dfs2(int u, int p, bool sub7 = false) {
color[u] = u;
sz_color[u] = 1;
par[u] = p;
high[u] = depth[u];
flag[u] = true;
node_cnt++;
edge_cnt += adj[u].size();
sz[u] = 1;
for (auto v: adj[u]) {
if (v == p) {
continue;
}
if (!flag[v]) {
depth[v] = depth[u] + 1;
dfs2(v, u, sub7);
sz[u] += sz[v];
high[u] = min(high[u], high[v]);
}
else {
high[u] = min(high[u], depth[v]);
if (depth[u] > depth[v] && sub7) {
int cur = u;
while (true) {
sz_color[color[cur]]--;
color[cur] = u;
sz_color[color[cur]]++;
if (cur == v) {
break;
}
cur = par[cur];
}
}
}
}
if (sub7) {
for (auto v: adj[u]) {
if (par[v] == u && color[v] != color[u]) {
ch_color[color[u]].push_back(color[v]);
}
}
}
}
void sub1() {
for (int x = 1; x <= n; x++) {
for (int a = 1; a <= n; a++) {
if (a != x) {
dfs1(x, a, a);
}
}
bad[x] = false;
}
int res = 0;
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (b == a) {
continue;
}
for (int c = 1; c <= n; c++) {
if (c == a || c == b) {
continue;
}
bool ok = true;
for (int x = 1; x <= n; x++) {
if (x == b) {
continue;
}
if (!can[x][a][b] && !can[x][b][c]) {
ok = false;
break;
}
}
if (ok) {
res++;
}
}
}
}
cout << res;
}
void dfs4(int u) {
node_cnt++;
comp.push_back(u);
for (auto v: ch_color[u]) {
dfs4(v);
}
}
long long solve(int root) {
comp.clear();
node_cnt = 0;
edge_cnt = 0;
dfs2(root, -1, true);
node_cnt = 0;
edge_cnt = 0;
dfs4(color[root]);
long long res = 0;
for (auto u: comp) {
res += 1LL * sz_color[u] * (node_cnt - sz_color[u]) * 2;
}
res -= 1LL * node_cnt * (node_cnt - 1);
return res;
}
long long dfs3(int u) {
int cnt = 1;
for (auto v: adj[u]) {
if (par[v] == u && high[v] >= depth[u]) {
cnt += sz[v];
}
}
long long res = 1LL * cnt * (cnt - 1);
for (auto v: adj[u]) {
if (par[v] == u && high[v] < depth[u]) {
res += dfs3(v);
}
}
return res;
}
void sub8() {
long long res = 0;
for (int u = 1; u <= n; u++) {
node_cnt = 0;
for (int i = 1; i <= n; i++) {
flag[i] = false;
}
depth[u] = 0;
dfs2(u, -1);
res += 1LL * (node_cnt - 1) * (node_cnt - 2);
for (auto v: adj[u]) {
if (par[v] == u) {
res -= dfs3(v);
}
}
}
cout << res;
}
void just_do_it() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (n <= 50 && false) {
sub1();
return;
}
if (n <= 1000 && false) {
sub8();
return;
}
long long res = 0;
for (int i = 1; i <= n; i++) {
if (!flag[i]) {
res += solve(i);
}
}
cout << res;
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
20880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
13848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
13992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
