Submission #1104992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104992		SoMotThanhXuan	Swapping Cities (APIO20_swap)	C++17	100 / 100	311 ms	98740 KiB

swap

#include <bits/stdc++.h>

using namespace std;

const int maxN = 3e5 + 5;
int pre[maxN], sz[maxN], curr[maxN], val[maxN], par[20][maxN], depth[maxN], mx[20][maxN], deg[maxN], node;
bool take[maxN], good[maxN], is_true[20][maxN], is_there_any_answer = false;
vector<int> adj[maxN];

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

void union_set(int u, int v, int w) {
    int a = find_set(u), b = find_set(v);
    ++node;

    if (a == b) {
        adj[node].push_back(curr[a]);
        curr[a] = node;
        good[a] = true;
        take[node] = true;
        val[node] = w;
        return ;
    }

    if (sz[a] < sz[b]) swap(a, b);

    pre[b] = a;
    sz[b] += sz[a];
    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;
    take[node] = good[a];
    val[node] = w;
}

void dfs(int u, int pre) {
    is_there_any_answer |= take[u];

    for (auto v: adj[u]) {
        if (v == pre) continue;
        par[0][v] = u;
        mx[0][v] = val[u];
        is_true[0][v] = take[u];
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

struct Ed {
    int u, v, w;

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

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    for (int k = 18; k >= 0; k--) {
        if (depth[par[k][u]] >= depth[v])
            u = par[k][u];
    }

    if (u == v) return u;

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

    return par[0][u];
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 1; i <= n + m; i++) {
        pre[i] = i;
        sz[i] = 1;
        if (i <= n) curr[i] = i;
    }

    for (int i = 0; i < m; i++) {
        U[i]++; V[i]++;
        edge[i + 1] = {U[i], V[i], W[i]};
    }

    sort(edge + 1, edge + m + 1);

    node = n;

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

    depth[n + m] = 1;
    dfs(n + m, n + m);

    //for (int i = 1; i <= n + m; i++) {
        //cout << "Debug " << val[i] << ' '<< take[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]]) ? true : false;
        }
}

int getMinimumFuelCapacity(int x, int y) {
    if (!is_there_any_answer) return -1;

    x++; y++;

    int lca = get_lca(x, y), ans = 0; bool valid = false;

    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];
            y = par[k][y];
        }

    if (valid) return ans;

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

    ans = max(ans, mx[0][lca]);
    return ans;
}


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

    int mn, nm, q;
    cin >> mn >> nm >> q;

    vector<int> a, b, c;

    for (int i = 1; i <= nm; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        a.push_back(u);
        b.push_back(v);
        c.push_back(w);
    }

    init(mn, nm, a, b, c);


    while (q--) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        cout << getMinimumFuelCapacity(x, y) << '\n';
    }

    return 0;
}
*/

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