Submission #1217421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217421		_callmelucian	Swapping Cities (APIO20_swap)	C++17	37 / 100	2095 ms	8120 KiB

swap

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

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct DSU {
    vector<int> lab, contain;
    DSU (int sz) : lab(sz + 1, -1), contain(sz + 1) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    bool unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return contain[a] = 1, 0;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        contain[a] |= contain[b];
        return 1;
    }

    void setNode (int u) { contain[get(u)] = 1; }

    bool valid (int a, int b) {
        int root = get(a);
        return root == get(b) && contain[root];
    }
};

const int mn = 2e5 + 5;
int curDeg[mn], n, m;
vector<tpl> edges;

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++)
        edges.emplace_back(W[i], U[i], V[i]);
    sort(all(edges));
}

int getMinimumFuelCapacity (int X, int Y) {
    fill(curDeg, curDeg + 1 + n, 0);

    DSU dsu(n);
    for (auto [c, a, b] : edges) {
        curDeg[a]++, curDeg[b]++;
        if (curDeg[a] == 3) dsu.setNode(a);
        if (curDeg[b] == 3) dsu.setNode(b);
        dsu.unite(a, b);
        if (dsu.valid(X, Y)) return c;
    }
    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