Submission #657003

#TimeUsernameProblemLanguageResultExecution timeMemory
657003600MihneaSwapping Cities (APIO20_swap)C++17
0 / 100
2066 ms14100 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int INF = (int) 1e9 + 7; vector<int> edge_ids; vector<int> papa_dsu; vector<int> wait_outside; vector<int> par; vector<int> dep; vector<int> weight_up; vector<int> oth_min; vector<vector<pair<int, int>>> g; bool deja = 0; int get_root(int a) { if (papa_dsu[a] == a) { return a; } else { return papa_dsu[a] = get_root(papa_dsu[a]); } } void dfs(int a, int p = -1) { par[a] = p; vector<pair<int, int>> kids; for (auto &it : g[a]) { int b = it.first; if (b == p) { continue; } weight_up[b] = it.second; dep[b] = 1 + dep[a]; dfs(b, a); kids.push_back(it); } g[a] = kids; int mn = INF; for (int rev = 0; rev < 2; rev++) { for (auto &it : g[a]) { int b = it.first; oth_min[b] = min(oth_min[b], mn); mn = min(mn, weight_up[b]); } reverse(g[a].begin(), g[a].end()); } } void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { par.resize(n, -1); dep.resize(n, 0); weight_up.resize(n, INF); oth_min.resize(n, INF); assert(deja == 0); deja = 1; assert((int) U.size() == m); assert((int) V.size() == m); assert((int) W.size() == m); g.resize(n); edge_ids.resize(m); iota(edge_ids.begin(), edge_ids.end(), 0); sort(edge_ids.begin(), edge_ids.end(), [&] (int i, int j) { return W[i] < W[j]; }); papa_dsu.resize(n); iota(papa_dsu.begin(), papa_dsu.end(), 0); wait_outside.resize(n, INF); for (int j = 0; j < m; j++) { int index = edge_ids[j]; int a = U[index]; int b = V[index]; assert(0 <= a && a < n); assert(0 <= b && b < n); if (get_root(a) != get_root(b)) { g[a].push_back({b, W[index]}); g[b].push_back({a, W[index]}); papa_dsu[get_root(a)] = get_root(b); } else { wait_outside[a] = min(wait_outside[a], W[index]); wait_outside[b] = min(wait_outside[b], W[index]); } } dfs(0); } int lca_dumb(int x, int y) { while (x != y) { if (dep[x] > dep[y]) { swap(x, y); } // dep[x] <= dep[y]; y = par[y]; } return x; } int iq = 0; int getMinimumFuelCapacity(int x, int y) { iq++; if (x == y) { return 0; } int z = lca_dumb(x, y); bool init_good = (x != z && y != z); int ix = x; int iy = y; int sol = 0, sol2 = INF; sol2 = min(sol2, wait_outside[x]); sol2 = min(sol2, wait_outside[y]); // cout << par[x] << " " << par[y] << "\n"; while (x != y) { if (dep[x] < dep[y]) { swap(x, y); } //cout << " = " << x << " " << y << "\n"; assert(dep[x] >= dep[y]); // cobor x if (par[x] != x) { sol = max(sol, weight_up[x]); } if (par[x] != z) { sol2 = min(sol2, oth_min[x]); } x = par[x]; sol2 = min(sol2, wait_outside[x]); } if (init_good) { sol2 = min(sol2, weight_up[z]); while (par[ix] != z) { ix = par[ix]; } while (par[iy] != z) { iy = par[iy]; } for (auto &it : g[z]) { int b = it.first; if (b == ix || b == iy) { continue; } sol2 = min(sol2, weight_up[b]); } } if (sol2 == INF) { return -1; } return max(sol, sol2); //cout << " = " << ix << " " << iy << "\n"; cout << sol << "\n"; cout << sol2 << "\n"; exit(0); return max(sol, sol2); }
#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...