Submission #1201645

#TimeUsernameProblemLanguageResultExecution timeMemory
1201645A_M_NamdarSwapping Cities (APIO20_swap)C++20
0 / 100
12 ms27016 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10, inf = 1e9 + 100, LG = 20; int n, m, par[N], lp[N], h[N], par2[N][LG], dp[N][LG], wei[N], h2[N]; vector<int> ver[N]; vector<pair<int, int>> adj[N]; struct EDGE { int u, v, w; friend bool operator<(EDGE p1, EDGE p2) { return p1.w < p2.w; } }; vector<EDGE> edge; int get_par(int u) { return (par[u] == -1? u: get_par(par[u])); } void merge(int u, int v, int w) { int uu = u, vv = v; u = get_par(u), v = get_par(v); if (ver[v].size() > ver[u].size()) swap(u, v); if (u == v) { if (lp[u] > 1e9) for (int x: ver[u]) lp[x] = w; return; } adj[uu].push_back({vv, w}); adj[vv].push_back({uu, w}); if (lp[u] <= 1e9 && lp[v] > 1e9) for (int x: ver[v]) lp[x] = w; if (lp[u] > 1e9 && lp[v] <= 1e9) for (int x: ver[u]) lp[x] = w; par[v] = u; wei[v] = w; for (int x: ver[v]) ver[u].push_back(x), h2[x]++; } void dfs(int u) { for (pair<int, int> e: adj[u]) if (e.first != par2[u][0]) { par2[e.first][0] = u; h[e.first] = h[u] + 1; dfs(e.first); } } void pre() { sort(edge.begin(), edge.end()); memset(par, -1, sizeof par); memset(par2, -1, sizeof par2); memset(lp, 63, sizeof lp); for (int i = 0; i < n; i++) ver[i].push_back(i); for (int i = 0; i < m; i++) merge(edge[i].u, edge[i].v, edge[i].w); dfs(0); for (int i = 1; i < n; i++) { dp[i][0] = inf; for (pair<int, int> e: adj[par2[i][0]]) { int v = e.first, w = e.second; if (v != i && v != par2[par2[i][0]][0]) { dp[i][0] = w; break; } } } for (int j = 1; j < LG; j++) for (int i = 0; i < n; i++) if (h[i] >= (1 << i)) { par2[i][j] = par2[par2[i][j - 1]][j - 1]; dp[i][j] = min(dp[i][j - 1], dp[par2[i][j - 1]][j - 1]); } } void init(int nn, int mm, vector<int> u, vector<int> v, vector<int> w) { n = nn; m = mm; for (int i = 0; i < m; i++) edge.push_back({u[i], v[i], w[i]}); pre(); } int lca(int u, int v, int res = 0) { // cout << u << ' ' << v << endl; if (h2[u] > h2[v]) swap(u, v); while (h2[v] > h2[u] + 1) { res = max(res, wei[v]); v = par[v]; } if (u == par[v]) return res; if (h2[v] > h2[u]) { res = max(res, wei[v]); v = par[v]; } while (par[u] != par[v]) { res = max(res, max(wei[u], wei[v])); u = par[u], v = par[v]; } return max(res, max(wei[u], wei[v])); } int lca2(int u, int v, int res = inf) { if (h[u] > h[v]) swap(u, v); for (int i = LG - 1; i >= 0; i--) if (h[v] - (1 << i) > h[u]) { res = min(res, dp[v][i]); v = par2[v][i]; } if (par2[v][0] == u) return res; if (h[v] > h[u]) { res = min(res, dp[v][0]); v = par2[v][0]; } for (int i = LG - 1; i >= 0; i--) if (h[u] >= (1 << i) && par2[u][i] != par2[v][i]) { res = min(res, min(dp[u][i], dp[v][i])); u = par2[u][i], v = par2[v][i]; } int l = par2[u][0]; for (pair<int, int> e: adj[l]) { int x = e.first, w = e.second; if (x != v && x != v) return min(res, w); } return res; } int getMinimumFuelCapacity(int u, int v) { int res = lca(u, v); // cout << res << '\n'; int tmp = min(max(lp[u], lp[v]), lca2(u, v)); // cout << lp[u] << ' ' << lp[v] << ' ' << lca2(u, v) << '\n'; if (max(res, tmp) > 1e9) return -1; return max(res, tmp); }
#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...