oj.uz

Submission #965937

# Submission time Handle Problem Language Result Execution time Memory
965937 2024-04-19T08:17:06 Z Pring Swapping Cities (APIO20_swap) C++17
0 / 100
 265 ms 31492 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], idfn[MXN], C;
        int ep[MXN], ed[MXN];

        namespace DP {
            pair<pii, pii> down[MXN];

            void PUSH(int id, pii p) {
                if (p > down[id].fs) {
                    down[id].sc = down[id].fs;
                    down[id].fs = p;
                } else down[id].sc = min(down[id].sc, p);
            }

            int DFS1(int id, int par) {
                int ans = vs[id].CMP2(ep[par]);
                down[id].fs = mp(INF, -1);
                down[id].sc = mp(INF, -1);
                for (auto &[w, i] : edge[id]) {
                    if (i == par) continue;
                    int val = DFS1(i, id);
                    PUSH(id, mp(max(w, val), id));
                    ans = min(ans, val);
                }
                return ans;
            }

            int QUERY(int id, int x) {
                int ans = vs[id].CMP2((d[id] > d[x] ? ep[id] : ep[x]));
                if (x == down[id].fs.sc) ans = min(ans, down[id].sc.fs);
                else ans = min(ans, down[id].fs.fs);
                return ans;
            }

            void DFS2(int id, int par) {
                if (par) {
                    PUSH(id, mp(max(ep[id], QUERY(par, id)), par));
                }
                for (auto &[_, i] : edge[id]) {
                    if (i == par) continue;
                    DFS2(i, id);
                }
            }
        }

        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++;
            idfn[dfn[id]] = id;
            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);
            DP::DFS1(1, 0);
            DP::DFS2(1, 0);
        }

        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], INF);
            while (top[x] != top[rt]) {
                ans = min(ans, smg.query(dfn[top[x]], dfn[x] + 1));
                ww = 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, idfn[dfn[rt] + 1]);
        }
    }

    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, lst] = TREE::CHAIN(y, x);
            return min(ans, min(TREE::DP::QUERY(x, TREE::p[x]), TREE::DP::QUERY(y, lst)));
        }
        auto [ansl, _1] = TREE::CHAIN(lca, x);
        auto [ansr, _2] = TREE::CHAIN(lca, y);
        return min(min(min(ansl, ansr), min(TREE::DP::QUERY(x, TREE::p[x]), TREE::DP::QUERY(y, TREE::p[y]))), vs[lca].CMP(TREE::ep[_1], TREE::ep[_2]));
    }
}

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:249:9: note: in expansion of macro 'debug'
  249 |         debug(x, y, lca);
      |         ^~~~~
swap.cpp: In function 'pii {anonymous}::TREE::CHAIN(int, int)':
swap.cpp:203:28: warning: 'ww' may be used uninitialized in this function [-Wmaybe-uninitialized]
  203 |             int ans = INF, ww;
      |                            ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 3 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 3 ms 11804 KB Output is correct
9 Correct 68 ms 24912 KB Output is correct
10 Correct 83 ms 29128 KB Output is correct
11 Correct 78 ms 28364 KB Output is correct
12 Correct 84 ms 29644 KB Output is correct
13 Correct 80 ms 31492 KB Output is correct
14 Correct 77 ms 24520 KB Output is correct
15 Correct 201 ms 30548 KB Output is correct
16 Incorrect 265 ms 28620 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 11612 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Incorrect 188 ms 26056 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 11612 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 3 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 3 ms 11804 KB Output is correct
9 Runtime error 7 ms 14684 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 7 ms 14684 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 11612 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 3 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 3 ms 11612 KB Output is correct
8 Correct 3 ms 11804 KB Output is correct
9 Correct 68 ms 24912 KB Output is correct
10 Correct 83 ms 29128 KB Output is correct
11 Correct 78 ms 28364 KB Output is correct
12 Correct 84 ms 29644 KB Output is correct
13 Correct 80 ms 31492 KB Output is correct
14 Correct 77 ms 24520 KB Output is correct
15 Correct 201 ms 30548 KB Output is correct
16 Incorrect 265 ms 28620 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 7 ms 14684 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -