Submission #356276

#TimeUsernameProblemLanguageResultExecution timeMemory
356276valerikkDuathlon (APIO18_duathlon)C++17
10 / 100
1082 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int n, m; vector<pair<int, int>> g[N]; vector<int> gr[N]; int dep[N], low[N]; bool vis[N]; int col[N], cnt; int sz[N]; long long ans; int S; void dfs(int v, int p = -1) { vis[v] = true; low[v] = dep[v]; for (auto [u, i] : g[v]) { if (!vis[u]) { dep[u] = dep[v] + 1; dfs(u, i); low[v] = min(low[v], low[u]); if (dep[v] <= low[u] || p == -1) { col[i] = ++cnt; } else { col[i] = col[p]; } } else { if (i != p) { low[v] = min(low[v], dep[u]); if (dep[u] > dep[v]) col[i] = col[p]; } } } } int get_size(int v, int p = -1) { sz[v] = v <= n; for (int u : gr[v]) { if (u != p) { sz[v] += get_size(u, v); } } return sz[v]; } void find_ans(int v, int p = -1) { vis[v] = true; for (int u : gr[v]) { if (u != p) find_ans(u, v); } if (v <= n) { for (int u : gr[v]) { if (u == p) ans -= (long long)(S - sz[v]) * (S - sz[v] - 1); else ans -= (long long)sz[u] * (sz[u] - 1); } } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; g[u].push_back({v, i}); g[v].push_back({u, i}); } cnt = n; for (int i = 1; i <= n; ++i) { if (!vis[i]) { dep[i] = 0; dfs(i); } } for (int i = 1; i <= n; ++i) { vector<int> v; for (auto [u, i] : g[i]) v.push_back(col[i]); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int c : v) { // cout << min(i, c) << " " << max(i, c) << endl; gr[i].push_back(c); gr[c].push_back(i); } } for (int i = 1; i <= cnt; ++i) { if (!vis[i]) { S = get_size(i); ans += (long long)S * (S - 1) * (S - 2); find_ans(i); } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...