Submission #321118

#	Time	Username	Problem	Language	Result	Execution time	Memory
321118		12tqian	Swapping Cities (APIO20_swap)	C++14	6 / 100	156 ms	20144 KiB

swap

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

const int INF = 1e9;
struct DSU {
    vector<int> e;
    vector<vector<int>> done;
    vector<int> cycle;
    vector<bool> ok;
    void init(int n) {
        e = vector<int>(n, -1);
        done.resize(n);
        cycle = vector<int>(n, INF);
        ok = vector<bool>(n, false);
        for (int i = 0; i < n; i++) {
            done[i].push_back(i);
        }
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y, int w) {
        cycle[x] = min(cycle[x], w);
        cycle[y] = min(cycle[y], w);
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        for (int v : done[y]) {
            done[x].push_back(v);
        }
        e[x] += e[y]; e[y] = x;
        return true;
    }
    void purge(int x, int w) {
        x = get(x);
        for (int v : done[x]) {
            cycle[v] = w;
            ok[v] = true;
        }
        done[x].clear();
    }
};
DSU D;
void init(int N, int M,
    std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<array<int, 3>> edges(M);
    for (int i = 0; i < M; i++) {
        edges[i][0] = W[i];
        edges[i][1] = U[i];
        edges[i][2] = V[i];
    }
    sort(edges.begin(), edges.end());
    D.init(N);
    for (auto e : edges) {
        int u = e[1];
        int v = e[2];
        int w = e[0];
        if (D.same_set(u, v)) {
            D.purge(u, w);
        } else {
            D.unite(u, v, w);
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = max(D.cycle[X], D.cycle[Y]);
    if (ans >= INF || D.ok[X] == false && D.ok[Y] == false) {
        return -1;
    } else {
        return ans;
    }
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:75:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   75 |     if (ans >= INF || D.ok[X] == false && D.ok[Y] == false) {
      |                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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