Submission #289217

#	Time	Username	Problem	Language	Result	Execution time	Memory
289217		dolphingarlic	Swapping Cities (APIO20_swap)	C++14	100 / 100	482 ms	55592 KiB

swap

#include "swap.h"

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

pair<int, pair<int, int>> edges[200000];
int cmp[300000], deg[300000], cost[300000], nodes;
bool has_deg_3[300000], has_cycle[300000];
vector<int> dsu_tree[300000];
int tin[300000], tout[300000], timer = 0, anc[300000][20];

int find(int A) {
    while (A != cmp[A]) A = cmp[A], cmp[A] = cmp[cmp[A]];
    return A;
}

void onion(int A, int B) {
    has_cycle[nodes] = has_cycle[find(A)] || has_cycle[find(B)];
    if (find(A) == find(B)) has_cycle[nodes] = true;
    has_deg_3[nodes] = has_deg_3[find(A)] || has_deg_3[find(B)];
    if (deg[A] == 3 || deg[B] == 3) has_deg_3[nodes] = true;
    dsu_tree[nodes].push_back(find(A));
    if (find(A) != find(B)) dsu_tree[nodes].push_back(find(B));
    cmp[find(A)] = cmp[find(B)] = nodes;
    nodes++;
}

void dfs(int node = nodes - 1, int parent = -1) {
    tin[node] = timer++;
    for (int i = 1; i < 20; i++) anc[node][i] = -1;
    for (int i = 1; i < 20 && ~anc[node][i - 1]; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
    for (int i : dsu_tree[node]) {
        anc[i][0] = node;
        dfs(i, node);
    }
    tout[node] = timer++;
}

bool is_ancestor(int A, int B) { return tin[A] <= tin[B] && tout[A] >= tout[B]; }

int lca(int A, int B) {
    if (is_ancestor(A, B)) return A;
    for (int i = 19; ~i; i--) if (~anc[A][i] && !is_ancestor(anc[A][i], B)) A = anc[A][i];
    return anc[A][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++) edges[i] = {W[i], {U[i], V[i]}};
    sort(edges, edges + M);
    nodes = N;
    iota(cmp, cmp + N + M, 0);
    for (int i = 0; i < M; i++) {
        deg[edges[i].second.first]++;
        deg[edges[i].second.second]++;
        cost[nodes] = edges[i].first;
        onion(edges[i].second.first, edges[i].second.second);
    }
    for (int i = 0; i < nodes; i++) for (int j = 0; j < 20; j++) anc[i][j] = -1;
    dfs();
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!has_cycle[nodes - 1] && !has_deg_3[nodes - 1]) return -1;
    int l = lca(X, Y);
    if (has_cycle[l] || has_deg_3[l]) return cost[l];
    for (int i = 19; ~i; i--) if (~anc[l][i] && !has_cycle[anc[l][i]] && !has_deg_3[anc[l][i]])
        l = anc[l][i];
    return cost[anc[l][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