Submission #1233382

#TimeUsernameProblemLanguageResultExecution timeMemory
1233382badge881Swapping Cities (APIO20_swap)C++20
37 / 100
2093 ms14000 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int MN = 2e5 + 5; const int INF = 1e9 + 10; int n, m; int bos[MN], sz[MN], large[MN]; vector<tuple<int, int, int>> edges; vector<vector<int>> g; vector<int> deg, maxDeg; vector<bool> av, inPath, vis, cyc; int boss(int u) { if (bos[u] == u) return u; return bos[u] = boss(bos[u]); } void merge(int e) { auto [_, u, v] = edges[e]; deg[u]++; deg[v]++; maxDeg[boss(u)] = max(maxDeg[boss(u)], deg[u]); maxDeg[boss(v)] = max(maxDeg[boss(v)], deg[v]); u = boss(u); v = boss(v); if (u == v) { cyc[u] = true; return; } if (sz[u] > sz[v]) swap(u, v); bos[u] = v; sz[v] += sz[u]; maxDeg[v] = max(maxDeg[v], maxDeg[u]); cyc[v] = cyc[u] || cyc[v]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N; m = M; for (int i = 0; i < m; i++) edges.push_back({W[i], U[i], V[i]}); sort(edges.begin(), edges.end()); g.resize(n); for (int i = 0; i < m; i++) { auto [_, u, v] = edges[i]; g[u].push_back(i); g[v].push_back(i); } } int getMinimumFuelCapacity(int X, int Y) { int a = X, b = Y; deg.assign(n, 0); maxDeg.assign(n, 0); cyc.assign(n, 0); for (int i = 0; i < n; i++) { bos[i] = i; sz[i] = 1; } for (int i = 0; i < m; i++) { merge(i); if (boss(a) == boss(b) && (maxDeg[boss(a)] >= 3 || cyc[boss(a)])) return get<0>(edges[i]); } return -1; }
#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...