Submission #829769

#TimeUsernameProblemLanguageResultExecution timeMemory
829769caganyanmazDuathlon (APIO18_duathlon)C++14
23 / 100
1101 ms1048576 KiB
#include <bits/stdc++.h> #define int int64_t #define pb push_back using namespace std; constexpr static int MXN = 1e5; int n, m; vector<int> g[MXN]; bitset<MXN> visited; int subtree_size[MXN]; int res; void dfs1(int node, int p) { visited[node] = true; subtree_size[node] = 1; for (int c : g[node]) { if (c == p) continue; dfs1(c, node); subtree_size[node] += subtree_size[c]; } } void dfs2(int node, int p, int sum) { for (int c : g[node]) { if (c == p) continue; dfs2(c, node, sum); res += subtree_size[c] * (sum - subtree_size[c] - 1); } int rem = sum - subtree_size[node]; res += (subtree_size[node] - 1) * rem; } int32_t main() { cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--,b--; g[a].pb(b); g[b].pb(a); } for (int i = 0; i < n; i++) { if (!visited[i]) { dfs1(i, i); dfs2(i, i, subtree_size[i]); } } cout << res << "\n"; }
#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...