Submission #1200933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200933		Braabebo10	자매 도시 (APIO20_swap)	C++20	0 / 100	560 ms	589824 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
vector<vector<ll> > anc, ans, ans2;
vector<ll> w, dep, cost, cost2, dist;
ll n, m, LOG = 20;

array<ll, 3> jump(ll u, ll k) {
    ll res1 = 0, res2 = 0;
    for (ll pw = 0; pw < LOG; pw++)
        if (k >> pw & 1)
            res1 = max(res1, ans[pw][u]), res2 = max(res2, ans2[pw][u]), u = anc[pw][u];
    return {u, res1, res2};
}

array<ll, 3> lca(ll u, ll v) {
    if (dep[u] < dep[v])swap(u, v);
    auto [nxt, res1, res2] = jump(u, max(0LL, dep[u] - dep[v] - 1));
    if (anc[0][nxt] == v)return {anc[0][nxt], max(res1, cost[nxt]), max(res2, ans2[0][nxt])};
    auto [nxt2, r1, r2] = jump(u, dep[u] - dep[v]);
    u = nxt2, res1 = r1, res2 = r2;
    bool enter = 0;
    for (ll pw = LOG - 1; pw >= 0; pw--)
        if (anc[pw][u] != anc[pw][v]) {
            res1 = max({res1, ans[pw][u], ans[pw][v]});
            res2 = max({res2, ans2[pw][u], ans2[pw][v]});
            u = anc[pw][u], v = anc[pw][v];
            enter = 1;
        }
    res1 = max({res1, cost[u], cost[v]});
    res2 = max({res2, ans2[0][u], ans2[0][v]});
    return {anc[0][u], res1, res2};
}

ll ay7aga = 0;
struct DSU {
    ll connected;
    vector<ll> par, sz;
    stack<array<ll, 2> > st;

    void init(ll n) {
        par = sz = vector<ll>(n + 1, 0);
        for (ll i = 1; i <= n; i++)
            par[i] = i, sz[i] = 1;
        connected = n;
    }

    ll findparent(ll u) {
        if (par[u] == u)return u;
        ll parent = findparent(par[u]);
        //if not rollback, uncomment
        //par[u] = parent;
        return parent;
    }

    ll getsize(ll u) {
        return sz[findparent(u)];
    }

    void unite(ll u, ll v) {
        ll par1 = findparent(u), par2 = findparent(v);

        st.push({-1, -1});
        if (par1 == par2)
            return;

        if (sz[par1] > sz[par2])
            swap(par1, par2);

        st.pop();
        st.push({connected, par1});
        connected--;

        sz[par2] += sz[par1];
        par[par1] = par2;
    }

    void rollback() {
        if (st.size()) {
            auto x = st.top();
            st.pop();
            if (x[0] == -1)return;
            connected = x[0];
            par[x[1]] = x[1];
        }
    }

    bool is_connected(ll u, ll v) {
        return findparent(u) == findparent(v);
    }
}dsu;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N, m = M;
    dsu.init(n);
    anc = ans = ans2 = vector<vector<ll> >(LOG, vector<ll>(n + 1));
    adj = vector<vector<array<ll, 3> > >(n + 1);
    dep = cost = cost2 = vector<ll>(n + 1, 0);
    dist = vector<ll>(n + 1, LLONG_MAX);
    for (ll i = 0; i < m; i++) {
        U[i]++, V[i]++;
        adj[U[i]].push_back({V[i], W[i], i});
        adj[V[i]].push_back({U[i], W[i], i});
        w.push_back(W[i]);
        dsu.unite(U[i], V[i]);
        ay7aga = max(ay7aga, (ll) W[i]);
    }
    function<void(ll, ll)> dfs = [&](ll u, ll p) {
        if (adj[u].size() > 2) {
            sort(all(adj[u]), [](auto a, auto b) {
                return a[1] < b[1];
            });
            cost2[u] = adj[u][2][1];
        } else cost2[u] = -1;
        anc[0][u] = p;
        ans[0][u] = max(cost[u], cost[p]);
        ans2[0][u] = max(cost2[u], cost2[p]);
        //        cout << u << ' ' << ans2[0][u] << ' ' << p << nl;
        for (ll pw = 1; pw < LOG; pw++) {
            anc[pw][u] = anc[pw - 1][anc[pw - 1][u]];
            ans[pw][u] = max(ans[pw - 1][anc[pw - 1][u]], ans[pw - 1][u]);
            ans2[pw][u] = max(ans2[pw - 1][anc[pw - 1][u]], ans2[pw - 1][u]);
        }
        for (auto [v, we, idx]: adj[u])
            if (v != p)
                cost[v] = we, dep[v] = dep[u] + 1, dfs(v, u);
    };
    dfs(1, 1);
    priority_queue<array<ll, 2>, vector<array<ll, 2> >, greater<> > pq;
    for (ll i = 1; i <= n; i++) {
        if (cost2[i] != -1)
            pq.push({dist[i] = cost2[i], i});
    }
    while (!pq.empty()) {
        auto [c, u] = pq.top();
        pq.pop();
        if (c > dist[u])continue;
        //        cout << u << ' ' << dist[u] << nl;
        for (auto [v, we, idx]: adj[u])
            if (max(we, c) < dist[v])
                pq.push({dist[v] = max(we, c), v});
    }

    sort(all(w));
    w.erase(unique(all(w)), w.end());
}

int getMinimumFuelCapacity(int x, int y) {
    return (dsu.is_connected(x, y)? ay7aga:-1);
}

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