#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define ll long long
using namespace std;
bool visited[100000];
ll n, m, k, a, b, g, cnt, f, rt, apcnt, low[100000], st[100000], sz[200000], dp[200000];
vector <ll> G, blocks;
bool ap[100000];
vector <ll> V, adj[100000], X[100000], E[200000];
void tar(ll u, ll p) {
G.push_back(u);
st[u] = low[u] = ++cnt;
V.push_back(u);
ll rch = 0;
for (auto v : adj[u]) {
if (!st[v]) {
++rch;
tar(v, u);
low[u] = min(low[u], low[v]);
if (p != -1 && low[v] >= st[u]) ap[u] = 1;
if (low[v] == st[u]) {
blocks.push_back(k);
while (!V.empty()) {
auto x = V.back();
V.pop_back();
X[x].push_back(k);
++sz[k];
if (x == v) break;
}
X[u].push_back(k);
++sz[k];
++k;
}
}
else if (v != p) {
low[u] = min(low[u], st[v]);
}
}
if (p == -1 && rch > 1) ap[u] = 1;
}
void calc(ll u, ll p) {
if (u >= n) dp[u] = sz[u] - E[u].size();
else dp[u] = 1;
for (auto v : E[u]) {
if (v != p) {
calc(v, u);
dp[u] += dp[v];
if (u >= n) {
f += (sz[u]-E[u].size()) * (dp[v] - 1) * 2;
f += (sz[u]-E[u].size()) * (G.size() - dp[v] - sz[u] + 1) * 4;
f += (dp[v] - 1) * (E[u].size() - 1) * 2;
}
}
}
for (auto v : E[u]) {
if (v != p) {
if (u < n) {
f += dp[v] * (dp[u] - 1 - dp[v]);
}
}
}
if (u >= n) {
f += (G.size() - dp[u]) * (E[u].size()-1) * 2;
f += sz[u] * (G.size() - dp[u]) * (dp[u] - sz[u] + E[u].size()) * 2;
}
}
int main() {
cin >> n >> m;
for (int i=0; i<m; ++i) {
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
k = n;
for (int i=0; i<n; ++i) {
if (!st[i]) {
G.clear();
blocks.clear();
V.clear();
tar(i, -1);
apcnt = 0;
for (auto u : G) {
if (ap[u]) {
++apcnt;
for (auto v : X[u]) {
E[u].push_back(v);
E[v].push_back(u);
}
}
}
for (auto u : blocks) {
if (sz[u] >= 3) f += sz[u] * (sz[u]-1) * (sz[u]-2);
if (sz[u]-(ll)E[u].size() >= 2) {
f += (sz[u]-E[u].size()) * (sz[u]-E[u].size()-1) * (G.size() - sz[u]) * 2;
}
}
calc(blocks[0], -1);
}
}
cout << f << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
31164 KB |
Output is correct |
2 |
Correct |
78 ms |
31380 KB |
Output is correct |
3 |
Incorrect |
69 ms |
24892 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
15 ms |
21852 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
73 ms |
36976 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
11 ms |
21848 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
86 ms |
37052 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
12892 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |