Submission #979895

#	Time	Username	Problem	Language	Result	Execution time	Memory
979895		Mher777	Swapping Cities (APIO20_swap)	C++17	7 / 100	657 ms	524288 KiB

swap

#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
*/

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27