#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
struct E {
int to, i;
};
const int N = 1e5 + 5;
vector<E> g[N];
vector<int> g2[N], t[N];
int tin[N], mt[N], col[N], sz[N], sum[N];
int timer = 0, n, m;
bool used[N];
void dfs(int node, int anc) {
used[node] = 1;
tin[node] = ++timer;
mt[node] = tin[node];
for (E e : g[node]) {
if (e.i != anc) {
if (!used[e.to]) {
dfs(e.to, e.i);
}
mt[node] = min(mt[node], mt[e.to]);
if (mt[e.to] <= tin[node]) {
g2[node].push_back(e.to);
g2[e.to].push_back(node);
}
}
}
}
void deep(int node, int c) {
col[node] = c;
used[node] = 1;
sz[col[node]]++;
for (int to : g2[node]) {
if (!used[to]) {
deep(to, c);
}
}
for (E e : g[node]) {
if (used[e.to] && col[e.to] != col[node]) {
t[col[node]].push_back(col[e.to]);
t[col[e.to]].push_back(col[node]);
}
}
}
ll ans = 0;
int walk(int node, int anc) {
int s = sz[node];
for (int to : t[node]) {
if (to != anc) {
s += walk(to, node);
}
}
return s;
}
void dive(int node, int anc, int whole) {
ans += sz[node] * (ll)(sz[node] - 1) * (sz[node] - 2);
sum[node] = sz[node];
used[node] = 1;
for (int to : t[node]) {
if (to != anc) {
dive(to, node, whole);
sum[node] += sum[to];
}
}
for (int to : t[node]) {
int s = 0;
if (to == anc)
s = whole - sum[node];
else
s = sum[to];
ans += sz[node] * (ll)s * (whole - s - sz[node]);
ans += (sz[node] * (ll)(sz[node] - 1) - sz[node] + 1) * s * 2;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
dfs(0, -1);
int cc = 0;
fill(used, used + n, 0);
for (int i = 0; i < n; i++) {
if (!used[i]) {
deep(i, cc++);
}
}
fill(used, used + cc, 0);
for (int i = 0; i < cc; i++) {
if (!used[i]) {
dive(i, -1, walk(i, -1));
}
}
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
21264 KB |
Output is correct |
2 |
Correct |
100 ms |
21212 KB |
Output is correct |
3 |
Correct |
95 ms |
19192 KB |
Output is correct |
4 |
Execution timed out |
1111 ms |
511864 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7544 KB |
Output is correct |
3 |
Correct |
8 ms |
7544 KB |
Output is correct |
4 |
Correct |
9 ms |
7544 KB |
Output is correct |
5 |
Correct |
8 ms |
7544 KB |
Output is correct |
6 |
Correct |
9 ms |
7616 KB |
Output is correct |
7 |
Correct |
9 ms |
7644 KB |
Output is correct |
8 |
Correct |
9 ms |
7544 KB |
Output is correct |
9 |
Correct |
8 ms |
7544 KB |
Output is correct |
10 |
Correct |
8 ms |
7548 KB |
Output is correct |
11 |
Correct |
8 ms |
7544 KB |
Output is correct |
12 |
Correct |
11 ms |
7544 KB |
Output is correct |
13 |
Correct |
11 ms |
7544 KB |
Output is correct |
14 |
Correct |
9 ms |
7472 KB |
Output is correct |
15 |
Correct |
8 ms |
7544 KB |
Output is correct |
16 |
Correct |
9 ms |
7440 KB |
Output is correct |
17 |
Correct |
9 ms |
7432 KB |
Output is correct |
18 |
Correct |
9 ms |
7544 KB |
Output is correct |
19 |
Correct |
9 ms |
7544 KB |
Output is correct |
20 |
Correct |
9 ms |
7544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
163 ms |
16380 KB |
Output is correct |
2 |
Correct |
167 ms |
16504 KB |
Output is correct |
3 |
Correct |
160 ms |
16412 KB |
Output is correct |
4 |
Correct |
103 ms |
16376 KB |
Output is correct |
5 |
Correct |
107 ms |
16376 KB |
Output is correct |
6 |
Correct |
116 ms |
20856 KB |
Output is correct |
7 |
Correct |
112 ms |
19452 KB |
Output is correct |
8 |
Correct |
106 ms |
18652 KB |
Output is correct |
9 |
Correct |
116 ms |
17800 KB |
Output is correct |
10 |
Correct |
142 ms |
16348 KB |
Output is correct |
11 |
Correct |
111 ms |
17836 KB |
Output is correct |
12 |
Correct |
97 ms |
17656 KB |
Output is correct |
13 |
Correct |
95 ms |
17668 KB |
Output is correct |
14 |
Correct |
79 ms |
16760 KB |
Output is correct |
15 |
Correct |
74 ms |
16120 KB |
Output is correct |
16 |
Correct |
49 ms |
14072 KB |
Output is correct |
17 |
Correct |
70 ms |
18284 KB |
Output is correct |
18 |
Correct |
67 ms |
18120 KB |
Output is correct |
19 |
Correct |
69 ms |
18400 KB |
Output is correct |
20 |
Correct |
77 ms |
18152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7544 KB |
Output is correct |
2 |
Correct |
9 ms |
7544 KB |
Output is correct |
3 |
Incorrect |
9 ms |
7544 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
99 ms |
16476 KB |
Output is correct |
2 |
Correct |
107 ms |
16248 KB |
Output is correct |
3 |
Incorrect |
109 ms |
16760 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7416 KB |
Output is correct |
6 |
Correct |
8 ms |
7416 KB |
Output is correct |
7 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |