Submission #965886

#	Time	Username	Problem	Language	Result	Execution time	Memory
965886		Pring	Swapping Cities (APIO20_swap)	C++17	0 / 100	214 ms	29640 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 3> p3i;

namespace {
    const int MXN = 100005, INF = 1e9;
    int n, m;
    vector<int> eu, ev, ew;
    vector<pii> edge[MXN];

    struct P {
        int a[3];
        P() {
            fill(a, a + 3, INF);
        }
        void ADD(int x) {
            if (x < a[0]) {
                a[2] = a[1];
                a[1] = a[0];
                a[0] = x;
            } else if (x < a[1]) {
                a[2] = a[1];
                a[1] = x;
            } else a[2] = min(a[2], x);
        }
        int CMP(int x, int y = INF) {
            if (x > y) swap(x, y);
            if (a[0] != x) return a[0];
            return (a[1] == y ? a[2] : a[1]);
        }
        int CMP2(int x) {
            if (a[0] == x) return a[1] + a[2];
            if (a[1] == x) return a[0] + a[2];
            return a[0] + a[1];
        }
    };

    vector<P> vs;
    int ori[MXN];

    struct DSU {
        int p[MXN];
        void init(int n) {
            fill(p + 1, p + n + 1, -1);
        }
        int find(int x) {
            return (p[x] < 0 ? x : p[x] = find(p[x]));
        }
        bool onion(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return false;
            if (p[x] > p[y]) swap(x, y);
            p[x] += p[y];
            p[y] = x;
            return true;
        }
    } dsu;

    struct SMG {
        int n, val[MXN * 2];
        void init(int _n, int *a) {
            n = _n;
            copy(a, a + n, val + n);
            for (int i = n - 1; i; i--) {
                val[i] = min(val[i << 1], val[i << 1 | 1]);
            }
        }
        void modify(int p, int v) {
            val[p + n] = v;
            for (int x = (p + n) >> 1; x; x >>= 1) val[x] = min(val[x << 1], val[x << 1 | 1]);
        }
        int query(int l, int r) {
            int ans = INF;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if (l & 1) ans = min(ans, val[l++]);
                if (r & 1) ans = min(ans, val[--r]);
            }
            return ans;
        }
    } smg;

    namespace TREE {
        vector<pii> edge[MXN];
        int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C;
        int ep[MXN], ed[MXN];

        void ADD_EDGE(int x, int y, int w) {
            edge[x].push_back(mp(w, y));
            edge[y].push_back(mp(w, x));
        }

        void DFS(int id, int par, int dep) {
            p[id] = par;
            d[id] = dep;
            sz[id] = 1;
            for (auto &[w, i] : edge[id]) {
                if (i == par) continue;
                DFS(i, id, dep + 1);
                sz[id] += sz[i];
                if (!son[id]) son[id] = i;
                else if (sz[son[id]] < sz[i]) son[id] = i;
            }
        }

        void HLD(int id, int par, int _t) {
            top[id] = _t;
            dfn[id] = C++;
            ep[id] = INF;
            ed[id] = INF;
            if (son[id]) HLD(son[id], id, _t);
            for (auto &[w, i] : edge[id]) {
                if (i == par) {
                    ep[id] = w;
                } else if (i == son[id]) {
                    ed[id] = w;
                } else {
                    HLD(i, id, i);
                }
            }
        }

        void BUILD() {
            DFS(1, 0, 0);
            HLD(1, 0, 1);
            FOR(i, 1, n + 1) ori[dfn[i]] = vs[i].CMP(ep[i], ed[i]);
            smg.init(n, ori);
        }

        int LCA(int x, int y) {
            while (top[x] != top[y]) {
                if (d[top[x]] < d[top[y]]) swap(x, y);
                x = p[top[x]];
            }
            return (d[x] > d[y] ? y : x);
        }

        pii CHAIN(int rt, int x) {
            int ans = INF, ww;
            vector<int> st;
            st.push_back(x);
            smg.modify(dfn[x], vs[x].CMP2(ep[x]));
            while (top[x] != top[rt]) {
                ans = min(ans, smg.query(dfn[top[x]], dfn[x] + 1));
                ww = ep[top[x]];
                x = p[top[x]];
                st.push_back(x);
                smg.modify(dfn[x], vs[x].CMP(ep[x], ww));
            }
            if (x == rt) {
                for (auto &i : st) {
                    smg.modify(dfn[i], ori[i]);
                }
                return mp(ans, ww);
            }
            ans = min(ans, smg.query(dfn[rt] + 1, dfn[x] + 1));
            for (auto &i : st) {
                smg.modify(dfn[i], ori[i]);
            }
            return mp(ans, ed[rt]);
        }
    }

    void BUILD() {
        vector<p3i> v;
        FOR(i, 0, m) v.push_back({ew[i], eu[i], ev[i]});
        sort(v.begin(), v.end());
        FOR(i, 0, m) {
            eu[i] = v[i][1];
            ev[i] = v[i][2];
            ew[i] = v[i][0];
        }
        vs = vector<P>(n + 1, P());
        dsu.init(n);
        FOR(i, 0, m) {
            vs[eu[i]].ADD(ew[i]);
            vs[ev[i]].ADD(ew[i]);
            if (dsu.onion(eu[i], ev[i])) TREE::ADD_EDGE(eu[i], ev[i], ew[i]);
        }
        TREE::BUILD();
    }
    int QUERY(int x, int y) {
        if (TREE::d[x] < TREE::d[y]) swap(x, y);
        int lca = TREE::LCA(x, y);
        debug(x, y, lca);
        if (lca == y) {
            auto [ans, epp] = TREE::CHAIN(y, x);
            // return min(ans, vs[y].CMP(epp));
            return min(ans, vs[y].CMP2(epp));
        }
        auto [ansl, eppl] = TREE::CHAIN(lca, x);
        auto [ansr, eppr] = TREE::CHAIN(lca, y);
        return min(min(ansl, ansr), vs[lca].CMP(eppl, eppr));
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    ::n = N;
    ::m = M;
    assert(m == n - 1);
    FOR(i, 0, m) {
        edge[++U[i]].push_back(mp(W[i], ++V[i]));
        edge[V[i]].push_back(mp(W[i], U[i]));
    }
    ::eu = U;
    ::ev = V;
    ::ew = W;
    BUILD();
}

int getMinimumFuelCapacity(int X, int Y) {
    int x = QUERY(++X, ++Y);
    return (x == ::INF ? -1 : x);
}

Compilation message (stderr)

swap.cpp: In function 'int {anonymous}::QUERY(int, int)':
swap.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
swap.cpp:203:9: note: in expansion of macro 'debug'
  203 |         debug(x, y, lca);
      |         ^~~~~
swap.cpp: In function 'pii {anonymous}::TREE::CHAIN(int, int)':
swap.cpp:157:28: warning: 'ww' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |             int ans = INF, ww;
      |                            ^~

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