제출 #729254

#제출 시각아이디문제언어결과실행 시간메모리
729254stevancv자매 도시 (APIO20_swap)C++14
6 / 100
551 ms44680 KiB
#include <bits/stdc++.h> #include "swap.h" #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e5 + 2; const int inf = 2e9; struct Dsu { int link[N]; void Init(int n) { for (int i = 1; i <= n; i++) link[i] = i; } int Find(int x) { if (x == link[x]) return x; return link[x] = Find(link[x]); } void Unite(int u, int v) { u = Find(u); v = Find(v); if (u == v) return; link[v] = u; } }dsu; vector<array<int, 3>> g[N]; int par[N][17], mxe[N][17], gmn[N][17], in[N], out[N], dep[N], mnb[N], parval[N], gmnval[N], tsz; void Dfs(int s, int e) { in[s] = ++tsz; par[s][0] = e; mxe[s][0] = parval[s]; gmn[s][0] = inf; if (g[s].size() >= 3) gmn[s][0] = g[s][2][0]; gmnval[s] = gmn[s][0]; for (int i = 1; i < 17; i++) { par[s][i] = par[par[s][i - 1]][i - 1]; mxe[s][i] = max(mxe[s][i - 1], mxe[par[s][i - 1]][i - 1]); gmn[s][i] = min(gmn[s][i - 1], gmn[par[s][i - 1]][i - 1]); } mnb[s] = inf; for (auto u : g[s]) { if (u[1] != e && u[2] == 1) { parval[u[1]] = u[0]; dep[u[1]] = dep[s] + 1; Dfs(u[1], s); smin(mnb[s], mnb[u[1]]); } if (u[2] == 0) { smin(mnb[s], u[0]); } } out[s] = tsz; } bool Ancestor(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int Lca(int u, int v) { if (Ancestor(u, v)) return u; if (Ancestor(v, u)) return v; for (int i = 16; i >= 0; i--) { if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i]; } return par[u][0]; } void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) { vector<array<int, 3>> e(m); for (int i = 0; i < m; i++) { u[i] += 1; v[i] += 1; e.push_back({w[i], u[i], v[i]}); } dsu.Init(n); sort(e.begin(), e.end()); for (auto u : e) { if (dsu.Find(u[1]) == dsu.Find(u[2])) { g[u[1]].push_back({u[0], u[2], 0}); g[u[2]].push_back({u[0], u[1], 0}); } else { dsu.Unite(u[1], u[2]); g[u[1]].push_back({u[0], u[2], 1}); g[u[2]].push_back({u[0], u[1], 1}); } } for (int i = 0; i < n; i++) { sort(g[i].begin(), g[i].end()); } for (int i = 0; i < 17; i++) gmn[0][i] = inf; Dfs(1, 0); } int GetMxFromPath(int u, int v) { int ans = 0; int raz = dep[u] - dep[v]; for (int i = 16; i >= 0; i--) { if ((1 << i) & raz) { smax(ans, mxe[u][i]); u = par[u][i]; } } return ans; } int GetMnFromPath(int u, int v) { int ans = inf; int raz = dep[u] - dep[v]; for (int i = 16; i >= 0; i--) { if ((1 << i) & raz) { smin(ans, gmn[u][i]); u = par[u][i]; } } return ans; } int Kth(int u, int k) { for (int i = 16; i >= 0; i--) { if ((1 << i) & k) u = par[u][i]; } return u; } int getMinimumFuelCapacity(int x, int y) { x += 1; y += 1; int lca = Lca(x, y); int o = max(GetMxFromPath(x, lca), GetMxFromPath(y, lca)); int xx = par[x][0]; if (x == lca) xx = Kth(y, dep[y] - dep[x] - 1); int yy = par[y][0]; if (y == lca) yy = Kth(x, dep[x] - dep[y] - 1); int ans = inf; if (xx != y && yy != x) { int oo = min(GetMnFromPath(xx, lca), GetMnFromPath(yy, lca)); smin(oo, gmnval[lca]); smin(ans, max(o, oo)); } smin(ans, max(o, max(mnb[x], mnb[y]))); 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...