Submission #967871

#	Time	Username	Problem	Language	Result	Execution time	Memory
967871		Pring	Swapping Cities (APIO20_swap)	C++17	100 / 100	307 ms	60680 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 = 300005, LG = 19;
    int n, m;
    vector<p3i> edges;
    int deg[MXN];

    struct DSU {
        int p[MXN];
        void init(int n) {
            fill(p, p + n, -1);
        }
        int find(int x) {
            return (p[x] < 0 ? x : p[x] = find(p[x]));
        }
        void onion(int rt, int x) {
            p[x] = rt;
        }
    } dsu;

    namespace TREE {
        vector<int> edge[MXN];
        int val[MXN];
        bitset<MXN> tag;
        int p[LG][MXN], d[MXN];

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

        void CONSTRUCT() {
            sort(edges.begin(), edges.end());
            dsu.init(n + m);
            FOR(i, 0, m) {
                auto [w, u, v] = edges[i];
                deg[u]++;
                deg[v]++;
                int uu = dsu.find(u), vv = dsu.find(v);
                int now = i + n;
                debug(now, u, v, uu, vv);
                val[now] = w;
                if (uu == vv) {
                    tag[now] = true;
                    dsu.onion(now, uu);
                    ADD_EDGE(now, uu);
                } else {
                    tag[now] = ((tag[uu]) | (tag[vv]) | (deg[u] >= 3) | (deg[v] >= 3));
                    dsu.onion(now, uu);
                    dsu.onion(now, vv);
                    ADD_EDGE(now, uu);
                    ADD_EDGE(now, vv);
                }
            }
        }

        void DFS(int id, int par, int dep) {
            p[0][id] = par;
            d[id] = dep;
            for (auto &i : edge[id]) {
                if (i == par) continue;
                DFS(i, id, dep + 1);
            }
        }

        void BUILD() {
            CONSTRUCT();
            DFS(n + m - 1, n + m - 1, 0);
            // FOR(i, 0, n + m) {
            //     for (auto &j : edge[i]) cout << j << ' ';
            //     cout << '\n';
            // }
            // FOR(i, 0, n + m) cout << p[0][i] << ' ';
            // cout << '\n';
            // FOR(i, 0, n + m) cout << tag[i] << ' ';
            // cout << '\n';
            // cout << "---\n";
            FOR(w, 1, LG) {
                FOR(i, 0, n + m) {
                    p[w][i] = p[w - 1][p[w - 1][i]];
                }
            }
        }
        
        int LEAP(int x, int k) {
            FOR(w, 0, LG) if (k & (1 << w)) x = p[w][x];
            return x;
        }

        int LCA(int x, int y) {
            if (d[x] < d[y]) swap(x, y);
            x = LEAP(x, d[x] - d[y]);
            if (x == y) return x;
            for (int w = LG - 1; w >= 0; w--) {
                if (p[w][x] == p[w][y]) continue;
                x = p[w][x];
                y = p[w][y];
            }
            return p[0][x];
        }

        int BSH(int x) {
            if (tag[x]) return x;
            for (int w = LG - 1; w >= 0; w--) {
                if (tag[p[w][x]]) continue;
                x = p[w][x];
            }
            return p[0][x];
        }

        int SOLVE(int x, int y) {
            int lca = LCA(x, y);
            debug(x, y, lca);
            int ans = BSH(lca);
            if (!tag[ans]) return -1;
            return val[ans];
        }
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    FOR(i, 0, m) edges.push_back(p3i{W[i], U[i], V[i]});
    TREE::BUILD();
}

int getMinimumFuelCapacity(int X, int Y) {
    return TREE::SOLVE(X, Y);
}

Compilation message (stderr)

swap.cpp: In function 'void {anonymous}::TREE::CONSTRUCT()':
swap.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
swap.cpp:62:17: note: in expansion of macro 'debug'
   62 |                 debug(now, u, v, uu, vv);
      |                 ^~~~~
swap.cpp: In function 'int {anonymous}::TREE::SOLVE(int, int)':
swap.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
swap.cpp:134:13: note: in expansion of macro 'debug'
  134 |             debug(x, y, lca);
      |             ^~~~~

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