Submission #1246938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246938		Turkhuu	Swapping Cities (APIO20_swap)	C++20	17 / 100	2095 ms	6368 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
int N, M;
vector<array<int, 3>> edges;
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = _N, M = _M;
    FOR(i, 0, M - 1) edges.push_back({W[i], U[i], V[i]});
    sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
    vector<int> deg(N), par(N), node(N, 1), edge(N);
    FOR(i, 0, N - 1) par[i] = i;
    function<int(int)> find = [&](int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    };
    auto unite = [&](int x, int y) {
        if ((x = find(x)) == (y = find(y))) {edge[x]++; return;}
        if (node[x] > node[y]) swap(x, y);
        par[x] = y, node[y] += node[x], edge[y] += edge[x] + 1;
    };
    for (auto [w, x, y] : edges) {
        deg[x]++, deg[y]++;
        unite(x, y);
        if (find(X) != find(Y)) continue;
        int z = find(X);
        if (edge[z] >= node[z]) return w;
        FOR(i, 0, N - 1) if (deg[i] >= 3 && find(i) == z) return w;
    }
    return -1;
}

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