Submission #777882

#TimeUsernameProblemLanguageResultExecution timeMemory
777882t6twotwoSwapping Cities (APIO20_swap)C++17
37 / 100
2081 ms10864 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; int N, M; vector<int> w, f, up, p; int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } constexpr int inf = 2e9; void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { N = n; M = m; p.resize(N); iota(p.begin(), p.end(), 0); vector<tuple<int, int, int>> edges(M); for (int i = 0; i < M; i++) { edges[i] = {W[i], U[i], V[i]}; } sort(edges.begin(), edges.end()); up.resize(N, -1); f.resize(N); w.resize(N, inf); int K = N; vector<int> deg(N); for (auto [z, a, b] : edges) { int x = find(a); int y = find(b); if (x == y) { if (!f[x]) { f[x] = 1; w[x] = z; } continue; } f.push_back(f[x] | f[y]); w.push_back(z); if (++deg[a] == 3 || ++deg[b] == 3) { f[K] = 1; } p.push_back(K); up.push_back(-1); p[x] = p[y] = up[x] = up[y] = K++; } } int getMinimumFuelCapacity(int x, int y) { if (find(x) != find(y)) { return -1; } while (x != y) { if (x < y) { x = up[x]; } else { y = up[y]; } } int ans = inf; while (x != -1) { if (f[x]) { ans = min(ans, w[x]); } x = up[x]; } if (ans == inf) { ans = -1; } return ans; }
#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...