oj.uz

Submission #965886

# Submission time Handle Problem Language Result Execution time Memory
965886 2024-04-19T07:45:33 Z Pring Swapping Cities (APIO20_swap) C++17
0 / 100
 214 ms 29640 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 59 ms 23044 KB Output is correct
10 Correct 86 ms 27232 KB Output is correct
11 Correct 85 ms 26416 KB Output is correct
12 Correct 95 ms 27856 KB Output is correct
13 Correct 80 ms 29640 KB Output is correct
14 Correct 70 ms 22472 KB Output is correct
15 Correct 206 ms 28572 KB Output is correct
16 Incorrect 200 ms 26652 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Incorrect 214 ms 24260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Runtime error 9 ms 14912 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 14912 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 59 ms 23044 KB Output is correct
10 Correct 86 ms 27232 KB Output is correct
11 Correct 85 ms 26416 KB Output is correct
12 Correct 95 ms 27856 KB Output is correct
13 Correct 80 ms 29640 KB Output is correct
14 Correct 70 ms 22472 KB Output is correct
15 Correct 206 ms 28572 KB Output is correct
16 Incorrect 200 ms 26652 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 14912 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -