Submission #1137422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137422		ConquerConquerer	Swapping Cities (APIO20_swap)	C++20	100 / 100	517 ms	86372 KiB

swap

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

const int maxN = 3e5 + 5;
bool good[maxN], is_true[20][maxN], status[maxN];
int par[20][maxN], mx[20][maxN], weight[maxN], curr[maxN], deg[maxN], depth[maxN];
int DSUpar[maxN], DSUsz[maxN];
vector<int> adj[maxN];

int find_set(int u) {
    return (DSUpar[u] == u) ? u : DSUpar[u] = find_set(DSUpar[u]);
}

void union_set(int u, int v, int w, int node) {
    int A = find_set(u), B = find_set(v);

    if (A == B) {
        adj[node].push_back(curr[A]);
        curr[A] = node;
        good[A] = true;
        weight[node] = w;
        status[node] = true;
        return ;
    }

    if (DSUsz[A] < DSUsz[B]) swap(A, B);
    DSUpar[B] = A;
    DSUsz[A] += DSUsz[B];
    adj[node].push_back(curr[A]);
    adj[node].push_back(curr[B]);
    curr[A] = node;

    if (good[A] || good[B] || ++deg[u] >= 3 || ++deg[v] >= 3) good[A] = true;
    status[node] = good[A];
    weight[node] = w;
}

struct Edg {
    int u, v, w;

    bool operator < (const Edg& rhs) const {
        return w < rhs.w;
    }
} edge[maxN];

void dfs(int u) {
    for (auto v: adj[u]) {
        par[0][v] = u;
        mx[0][v] = weight[u];
        is_true[0][v] = status[u];
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++)
        edge[i + 1] = {U[i] + 1, V[i] + 1, W[i]};

    sort(edge + 1, edge + M + 1);
    for (int i = 1; i <= N + M; i++) {
        DSUpar[i] = i;
        DSUsz[i] = 1;
        curr[i] = i;
    }

    for (int i = 1; i <= M; i++) {
        auto [u, v, w] = edge[i];
        union_set(u, v, w, N + i);
    }

    /*cout << "Init\n";

    for (int i = N + 1; i <= N + M; i++) {
        cout << "Node " << i << '\n';
        cout << weight[i] << ' ' << status[i] << '\n';
        cout << "Adj ";
        for (auto v: adj[i])
            cout << v << ' ';
        cout << '\n';
    }*/

    depth[N + M] = 1;
    dfs(N + M);

    //for (int i = 1; i <= N + M; i++)
        //cout << par[0][i] << ' ' << mx[0][i] << ' ' << is_true[0][i] << '\n';

    for (int k = 1; k <= 18; k++)
        for (int i = 1; i <= N + M; i++) {
            par[k][i] = par[k - 1][par[k - 1][i]];
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][par[k - 1][i]]);
            is_true[k][i] = is_true[k - 1][i] | is_true[k - 1][par[k - 1][i]];
        }
}

int getLCA(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);

    for (int k = 18; k >= 0; k--)
        if (depth[par[k][x]] >= depth[y])
            x = par[k][x];

    if (x == y) return x;

    for (int k = 18; k >= 0; k--) {
        if (par[k][x] != par[k][y]) {
            x = par[k][x];
            y = par[k][y];
        }
    }

    return par[0][y];
}

int getMinimumFuelCapacity(int x, int y) {
    x++; y++;
    if (find_set(x) != find_set(y)) return -1;

    int lca = getLCA(x, y), ans = 0; bool valid = false;
    //out << lca << '\n';

    for (int k = 18; k >= 0; k--)
        if (depth[par[k][x]] >= depth[lca]) {
            ans = max(ans, mx[k][x]);
            valid |= is_true[k][x];
            x = par[k][x];
        }

    for (int k = 18; k >= 0; k--)
        if (depth[par[k][y]] >= depth[lca]) {
            ans = max(ans, mx[k][y]);
            valid |= is_true[k][y];
            x = par[k][y];
        }

    if (valid) return ans;

    for (int k = 18; k >= 0; k--) {
        if (!par[k][x]) continue;
        if (!is_true[k][x]) {
            ans = max(ans, mx[k][x]);
            x = par[k][x];
        }
        //cout << "Jump " << k << ' ' << x << ' ';
    }
    //cout << '\n';
    if (is_true[0][x]) return max(ans, mx[0][x]);
    return -1;
}

/*
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> U, V, W;
    for (int i = 1; i <= M; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        U.push_back(u);
        V.push_back(v);
        W.push_back(w);
    }

    init(N, M, U, V, W);

    int Q;
    cin >> Q;

    while (Q--) {
        int x, y;
        cin >> x >> y;

        cout << getMinimumFuelCapacity(x, y) << '\n';
    }

    return 0;
}*/

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

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