#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
long long ans;
int n, m, tt, cnt_bcc, tam;
int tin[maxn], low[maxn], subtree[maxn];
vector<int> adj[maxn], bcc[maxn];
stack<int> stk;
void dfs(int on, int par = -1) {
tin[on] = low[on] = ++tt;
stk.push(on);
tam++;
for (int to : adj[on]) if (to != par) {
if (tin[to]) {
low[on] = min(low[on], tin[to]);
} else {
dfs(to, on);
low[on] = min(low[on], low[to]);
if (low[to] >= tin[on]) {
cnt_bcc++;
bcc[on].push_back(n + cnt_bcc);
while (bcc[n + cnt_bcc].empty() || bcc[n + cnt_bcc].back() != to) {
bcc[n + cnt_bcc].push_back(stk.top());
stk.pop();
}
}
}
}
}
void dfs2(int on) {
subtree[on] = (on <= n);
for (int to : bcc[on]) {
dfs2(to); // escolhendo o par (x, y) em cada ponto da minha subtree
subtree[on] += subtree[to];
if (on > n) ans -= 1ll * ((int) bcc[on].size()) * subtree[to] * (subtree[to] - 1);
}
// escolhendo o par (x, y) fora da minha subtree
if (on > n) ans -= 1ll * ((int) bcc[on].size()) * (tam - subtree[on]) * (tam - subtree[on] - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (!tin[i]) {
tam = 0;
dfs(i);
ans += 1ll * n * (n - 1) * (n - 2);
dfs2(i);
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
21352 KB |
Output is correct |
2 |
Correct |
84 ms |
22504 KB |
Output is correct |
3 |
Execution timed out |
1112 ms |
278260 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 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 |
5228 KB |
Output is correct |
8 |
Correct |
4 ms |
5228 KB |
Output is correct |
9 |
Correct |
4 ms |
5228 KB |
Output is correct |
10 |
Incorrect |
5 ms |
5100 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1131 ms |
791684 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5228 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5100 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5228 KB |
Output is correct |
13 |
Correct |
4 ms |
5228 KB |
Output is correct |
14 |
Correct |
4 ms |
5228 KB |
Output is correct |
15 |
Correct |
4 ms |
5228 KB |
Output is correct |
16 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
983 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |