Submission #1233367

#TimeUsernameProblemLanguageResultExecution timeMemory
1233367badge881자매 도시 (APIO20_swap)C++20
0 / 100
0 ms320 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 par[MN], sz[MN], large[MN]; vector<tuple<int, int, int>> edges; // <u, v, w> vector<vector<int>> g; vector<int> deg, maxDeg; vector<bool> av, inPath, vis, cyc; int boss(int u) { if (par[u] == u) return u; return par[u] = boss(par[u]); } void merge(int e) { auto [u, v, w] = 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); par[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,w] = 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++) par[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...