#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
const int MXN = 1e5;
vi adj[MXN], apAdj[MXN];
int low[MXN], tin[MXN], sz[MXN], initSz[MXN], apComp[MXN];
bool ap[MXN], vis[MXN], seen[MXN];
vector<vi> comp;
int pt = 0, m;
ll rem = 0, n;
void dfs(int p, int parent) {
comp[comp.size()-1].push_back(p);
vis[p] = true;
low[p] = tin[p] = pt++;
bool seenChild = false;
for (auto &i: adj[p]) if (i != parent) {
if (vis[i]) {
low[p] = min(low[p], tin[i]);
continue;
}
dfs(i, p);
if (seenChild and parent == p) ap[p] = true;
else seenChild = true;
low[p] = min(low[p], low[i]);
if (low[i] >= tin[p] and parent != p) ap[p] = true;
low[p] = min(low[p], low[i]);
}
}
void findSz(int p, int parent) {
sz[p] = initSz[p];
for (auto &i: apAdj[p]) if (i != parent) {
findSz(i, p);
sz[p] += sz[i];
}
}
void reroot(int p, int parent) {
for (auto &i: apAdj[p]) {
rem += sz[i] * (sz[i]-1) + (initSz[p]-1) * sz[i] * (sz[i]+1);
if (i != parent) {
sz[p] -= sz[i];
sz[i] += sz[p];
reroot(i, p);
sz[i] -= sz[p];
sz[p] += sz[i];
}
}
}
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for_(i, 0, m) {
int a, b; cin >> a >> b;
a -= 1; b -= 1;
adj[a].push_back(b); adj[b].push_back(a);
}
for_(i, 0, n) if (!vis[i]) {
comp.push_back({});
dfs(i, i);
}
for_(i, 0, n) if (adj[i].size() == 1) ap[i] = true;
for (auto &c: comp) {
vi apList;
for (int &i: c) if (ap[i]) apList.push_back(i);
queue<int> q;
q.push(apList[0]);
seen[apList[0]] = true;
while (q.size()) {
int p = q.front(); q.pop();
apComp[p] = p;
initSz[p]++;
for (auto &i: adj[p]) {
if (ap[i]) {
apAdj[p].push_back(i);
if (!seen[i]) {
seen[i] = true;
q.push(i);
}
}
else {
initSz[p]++;
apComp[i] = p;
}
}
}
findSz(apList[0], apList[0]);
reroot(apList[0], apList[0]);
}
cout << n*(n-1)*(n-2) - rem << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
36324 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5356 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5228 KB |
Output is correct |
| 10 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
15848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 3 |
Execution timed out |
1141 ms |
733932 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
15844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9964 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
