Submission #716989

#TimeUsernameProblemLanguageResultExecution timeMemory
716989stevancvPipes (CEOI15_pipes)C++14
90 / 100
2313 ms13696 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e5 + 2; const int inf = 1e9; struct Dsu { int link[N], sz[N]; void Reset(int n) { for (int i = 1; i <= n; i++) { link[i] = i; sz[i] = 1; } } int Find(int x) { if (x == link[x]) return x; return link[x] = Find(link[x]); } int GetSz(int x) { return sz[Find(x)]; } void Unite(int u, int v) { u = Find(u); v = Find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); link[v] = u; sz[u] += sz[v]; } }dsu; vector<int> g[N]; int par[N][16], dep[N], su[N]; void Dfs(int s, int e) { par[s][0] = e; dep[s] = dep[e] + 1; for (int i = 1; i < 16; i++) par[s][i] = par[par[s][i - 1]][i - 1]; for (int u : g[s]) { if (u == e) continue; Dfs(u, s); } } int Lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int r = dep[u] - dep[v]; for (int i = 0; i < 16; i++) { if ((1 << i) & r) u = par[u][i]; } if (u == v) return u; for (int i = 15; i >= 0; i--) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } int Solve(int s, int e) { for (int u : g[s]) { if (u == e) continue; int x = Solve(u, s); if (x == 0) cout << s << sp << u << en; su[s] += x; } return su[s]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; dsu.Reset(n); for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; if (dsu.Find(u) == dsu.Find(v)) { su[u] += 1; su[v] += 1; su[Lca(u, v)] -= 2; continue; } if (dsu.GetSz(u) < dsu.GetSz(v)) swap(u, v); dsu.Unite(u, v); Dfs(v, u); g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; i++) { if (dep[i] == 0) Solve(i, 0); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...