Submission #1273301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273301		thuhienne	Swapping Cities (APIO20_swap)	C++20	37 / 100	2094 ms	7368 KiB

swap

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

struct Edge {
    int u, v, w;
    bool operator < (const Edge &other) const {
        return w < other.w;
    }
};

const int MAXN = 100005;
const int MAXM = 200005;

int n, m;
Edge edge[MAXM];

int parent[MAXN], compSize[MAXN];
int deg[MAXN], cnt[MAXN][2];

int getRoot(int u) {
    return (u == parent[u] ? u : parent[u] = getRoot(parent[u]));
}

void raiseDeg(int u) {
    int r = getRoot(u);
    if (deg[u]) cnt[r][deg[u] - 1]--;
    deg[u]++;
    if (deg[u] <= 2) cnt[r][deg[u] - 1]++;
}

void mergeSet(int u, int v) {
    u = getRoot(u);
    v = getRoot(v);
    if (u == v) return;
    parent[u] = v;
    compSize[v] += compSize[u];
    cnt[v][0] += cnt[u][0];
    cnt[v][1] += cnt[u][1];
}

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

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 0; i < n; i++) {
        parent[i + 1] = i + 1;
        compSize[i + 1] = 1;
        deg[i + 1] = 0;
        cnt[i + 1][0] = cnt[i + 1][1] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int u = edge[i].u + 1; // đổi sang 1-based
        int v = edge[i].v + 1;
        raiseDeg(u);
        raiseDeg(v);
        mergeSet(u, v);

        int r = getRoot(X + 1);
        if (r == getRoot(Y + 1)) {
            if (cnt[r][1] != compSize[r] - 2 || cnt[r][0] != 2) {
                return edge[i].w;
            }
        }
    }
    return -1;
}

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