Submission #972937

#	Time	Username	Problem	Language	Result	Execution time	Memory
972937		DAleksa	Swapping Cities (APIO20_swap)	C++17	100 / 100	470 ms	357604 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

int tsz;

struct DSU {
    int n;
    vector<int> parent, sz;
    vector<bool> chain;
    vector<vector<int>> comp;
    vector<int> id;
    DSU(int _n) {
        n = _n;
        parent.resize(n);
        sz.resize(n);
        comp.resize(n);
        chain.resize(n);
        id.resize(n);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
            chain[i] = true;
            comp[i].push_back(i);
            id[i] = i;
        }
    }
    int find_parent(int u) {
        if(parent[u] == u) return u;
        return parent[u] = find_parent(parent[u]);
    }
    bool check(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        return u == v;
    }
    void join(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        if(sz[u] > sz[v]) swap(u, v);
        for(int i : comp[u]) comp[v].push_back(i);
        comp[u].clear();
        parent[u] = v;
        sz[v] += sz[u];
        id[v] = tsz;
    }
    void update_chain_state(int u) {
        u = find_parent(u);
        chain[u] = false;
    }
    int get_size(int u) {
        u = find_parent(u);
        return sz[u];
    }
};

const int N = 1e6 + 10, LOG = 20;
bool leaf[N];
DSU dsu(N), tree(2 * N);
int order[2 * N];
vector<int> g[2 * N];
int up[2 * N][LOG + 1];
int root;
int timer;
int tin[2 * N], tout[2 * N];
int ans[2 * N];
bool mark[2 * N];

void dfs(int u) {
    mark[u] = true;
    tin[u] = ++timer;
    for(int v : g[u]) {
        dfs(v);
        up[v][0] = u;
    }
    tout[u] = ++timer;
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int LCA(int u, int v) {
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = LOG; j >= 0; j--) {
//        cout << up[u][j] << "\n";
        if(up[u][j] == -1) continue;
        if(is_ancestor(up[u][j], v)) continue;
        u = up[u][j];
//        cout << u << " " << j << "\n";
    }
    return up[u][0];
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for(int i = 0; i < N; i++) {
        leaf[i] = true;
        for(int j = 0; j <= LOG; j++) up[i][j] = -1;
    }
    tsz = n;
    for(int i = 0; i < m; i++) order[i] = i;
    sort(order, order + m, [&](int i, int j) { return W[i] < W[j]; });
    for(int i = 0; i < m; i++) {
        int u = U[order[i]], v = V[order[i]];
        if(dsu.check(u, v)) {
            int par = dsu.find_parent(u);
            if(dsu.chain[par]) {
                for(int j : dsu.comp[par]) {
                    g[tsz].push_back(j);
                    tree.join(tsz, j);
                }
                ans[tsz] = W[order[i]];
                dsu.id[par] = tsz;
                tsz++;
                dsu.update_chain_state(par);
            }
        } else {
            if(!dsu.chain[dsu.find_parent(u)] || !dsu.chain[dsu.find_parent(v)]) {
                if(dsu.chain[dsu.find_parent(u)]) {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(u)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(u)]);
                }
                if(dsu.chain[dsu.find_parent(v)]) {
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(v)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(v)]);
                }
                dsu.join(u, v);
                int par = dsu.find_parent(u);
                dsu.update_chain_state(par);
                ans[tsz] = W[order[i]];
                tsz++;
            } else {
                if(leaf[u] && leaf[v]) {
                    if(dsu.get_size(u) > 1) leaf[u] = false;
                    if(dsu.get_size(v) > 1) leaf[v] = false;
                    dsu.join(u, v);
                } else {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    dsu.join(u, v);
                    ans[tsz] = W[order[i]];
                    tsz++;
                    dsu.update_chain_state(u);
                }
            }
        }
    }
//    for(int i = 0; i < tsz; i++) {
//        cout << i << ": ";
//        for(int j : g[i]) cout << j << " ";
//        cout << "\n";
//    }
    root = tsz - 1;
    for(int i = root; i >= 0; i--) if(!mark[i]) dfs(i);
//    for(int i = 0; i <= root; i++) {
//        for(int j = 0; j <= 5; j++) cout << up[i][j] << " ";
//        cout << "\n";
//    }
    for(int j = 1; j <= LOG; j++) {
        for(int i = 0; i <= root; i++) {
            if(up[i][j - 1] == -1) up[i][j] = -1;
            else up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
//    cout << "TU: " << LCA(4, 5) << "\n";
}

int getMinimumFuelCapacity(int X, int Y) {
//    return -1;
    if(!tree.check(X, Y)) return -1;
    return ans[LCA(X, Y)];
}

/*

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


3 2
0 1 5
0 2 5
1
1 2


6 7
0 1 1
1 2 2
0 2 3
3 4 4
4 5 5
3 5 6
2 3 7
15
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

*/

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