Submission #979895

#TimeUsernameProblemLanguageResultExecution timeMemory
979895Mher777Swapping Cities (APIO20_swap)C++17
7 / 100
657 ms524288 KiB
#include "swap.h" #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <iomanip> #include <array> #include <string> #include <algorithm> #include <cmath> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <utility> #include <random> #include <cassert> #include <fstream> using namespace std; mt19937 rnd(7069); typedef int itn; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef float fl; typedef long double ld; using vi = vector<int>; using vll = vector<ll>; using mii = map<int, int>; using mll = map<ll, ll>; using pii = pair<int, int>; using pll = pair<ll, ll>; #define ff first #define ss second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define mpr make_pair #define yes cout<<"Yes\n" #define no cout<<"No\n" #define all(x) (x).begin(), (x).end() const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 }; const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 }; const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18) + 5ll; const ll MOD = ll(1000000007); const ll MOD2 = ll(998244353); const int N = 100005; pii val[N], t[N * 4]; int dep[N], tp[N], id[N], p[N], sub[N], dp1[N], dp2[N]; vector<pii> g[N]; int n, m, timer; void dfs_sz(int u = 1, int par = 1) { dp1[u] = dp2[u] = MAX; if ((int)g[u].size() >= 3) { dp1[u] = dp2[u] = g[u][2].ff; } sub[u] = 1; p[u] = par; for (auto to : g[u]) { if (to.ss == par) continue; dep[to.ss] = dep[u] + 1; dfs_sz(to.ss, u); dp1[u] = min(dp1[u], max(to.ff, dp1[to.ss])); sub[u] += sub[to.ss]; } } void dfs_dp(int u = 1, int par = 1, int cur = 0) { dp2[u] = min(dp2[u], max(cur, dp2[par])); vi v; int sz = 0; for (auto to : g[u]) { if (to.ss == par) continue; ++sz; v.pub(max(dp1[to.ss], to.ff)); } if (!sz) return; vi pref(sz), suf(sz); pref[0] = v[0]; for (int i = 1; i < sz; ++i) { pref[i] = min(pref[i - 1], v[i]); } suf[sz - 1] = v[sz - 1]; for (int i = sz - 2; i >= 0; --i) { suf[i] = min(suf[i + 1], v[i]); } int ind = 0; for (auto to : g[u]) { if (to.ss == par) continue; dp2[to.ss] = dp2[u]; int mn = MAX; if (ind != 0) mn = min(mn, max(pref[ind - 1], to.ff)); if (ind != sz - 1) mn = min(mn, max(suf[ind + 1], to.ff)); dp2[to.ss] = min(dp2[to.ss], mn); } for (auto to : g[u]) { if (to.ss == par) continue; dfs_dp(to.ss, u, to.ff); } } void dfs_hld(int u = 1, int top = 1, int cur = 0) { tp[u] = top; id[u] = ++timer; val[id[u]] = { cur,min(dp1[u],dp2[u]) }; int mx = 0, v = -1; ll curx = 0; for (auto to : g[u]) { if (to.ss == p[u]) continue; if (sub[to.ss] > mx) { mx = sub[to.ss]; v = to.ss; curx = to.ff; } } if (v != -1) dfs_hld(v, top, curx); for (auto to : g[u]) { if (to.ss == p[u] || to.ss == v) continue; dfs_hld(to.ss, to.ss, to.ff); } } void bld(int l = 1, int r = n, int pos = 1) { if (l == r) { t[pos] = val[l]; return; } int mid = (l + r) / 2; bld(l, mid, 2 * pos); bld(mid + 1, r, 2 * pos + 1); t[pos].ff = max(t[2 * pos].ff, t[2 * pos + 1].ff); t[pos].ss = min(t[2 * pos].ss, t[2 * pos + 1].ss); } int qry(int l, int r, int type, int tl = 1, int tr = n, int pos = 1) { if (l == tl && r == tr) { return (type == 1 ? t[pos].ff : t[pos].ss); } int mid = (tl + tr) / 2; if (mid >= r) { return qry(l, r, type, tl, mid, 2 * pos); } if (mid < l) { return qry(l, r, type, mid + 1, tr, 2 * pos + 1); } if (type == 1) { return max(qry(l, mid, type, tl, mid, 2 * pos), qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1)); } return min(qry(l, mid, type, tl, mid, 2 * pos), qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1)); } void init(int N, int M, vi U, vi V, vi W) { n = N, m = M; for (int i = 0; i < m; ++i) { ++U[i]; ++V[i]; g[U[i]].pub({ W[i],V[i] }); g[V[i]].pub({ W[i],U[i] }); } for (int i = 1; i <= n; ++i) { sort(all(g[i])); } dfs_sz(); dfs_dp(); dfs_hld(); bld(); } int query1(int x, int y) { int ret = 0; while (tp[x] != tp[y]) { if (dep[tp[x]] < dep[tp[y]]) swap(x, y); ret = max(ret, qry(id[tp[x]], id[x], 1)); x = p[tp[x]]; } if (dep[x] > dep[y]) swap(x, y); if (x == y) return ret; ret = max(ret, qry(id[x] + 1, id[y], 1)); return ret; } int query2(int x, int y) { int ret = MAX; while (tp[x] != tp[y]) { if (dep[tp[x]] < dep[tp[y]]) swap(x, y); ret = min(ret, qry(id[tp[x]], id[x], 2)); x = p[tp[x]]; } if (dep[x] > dep[y]) swap(x, y); ret = min(ret, qry(id[x], id[y], 2)); return ret; } int getMinimumFuelCapacity(int X, int Y) { int x = X, y = Y; ++x, ++y; int num1 = query1(x, y), num2 = query2(x, y); if (num2 == MAX) return -1; return max(num1, num2); } /* 15 14 0 1 2 0 2 1 1 3 1 1 4 1 2 5 1 2 6 1 3 7 1 3 8 1 4 9 1 4 10 1 5 11 1 5 12 1 6 13 1 6 14 1 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...