Submission #777881

#	Time	Username	Problem	Language	Result	Execution time	Memory
777881		t6twotwo	Swapping Cities (APIO20_swap)	C++17	37 / 100	2069 ms	27984 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> ans, dep, p, up, w, f;
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
vector<vector<int>> par;
constexpr int inf = 2e9;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    N = n;
    M = m;
    p.resize(N + M);
    iota(p.begin(), p.end(), 0);
    vector<int> dif(N + M, -1), three(N + M), deg(N);
    w.resize(N + M);
    vector<vector<int>> ch(N + M);
    auto unite = [&](int x, int y, int t) {
        x = find(x);
        y = find(y);
        dif[t] = 1;
        for (int z : set<int>{x, y}) {
            three[t] |= three[z];
            dif[t] += dif[z];
            p[z] = t;
            up[z] = t;
            ch[t].push_back(z);
        }
    };
    vector<tuple<int, int, int>> edges(M);
    for (int i = 0; i < M; i++) {
        edges[i] = {W[i], U[i], V[i]};
    }
    sort(edges.begin(), edges.end());
    f.resize(N + M);
    up.resize(N + M, -1);
    for (int i = 0; i < M; i++) {
        auto [z, x, y] = edges[i];
        if (++deg[x] == 3) {
            three[find(x)] = 1;
        }
        if (++deg[y] == 3) {
            three[find(y)] = 1;
        }
        w[N + i] = z;
        unite(x, y, N + i);
        f[N + i] = three[N + i] == 1 || dif[N + i] >= 0;
    }
}
int getMinimumFuelCapacity(int x, int y) {
    if (find(x) != find(y)) {
        return -1;
    }
    while (x != y) {
        if (x < y) {
            x = up[x];
        } else {
            y = up[y];
        }
    }
    int ans = inf;
    while (x != -1) {
        if (f[x]) {
            ans = min(ans, w[x]);
        }
        x = up[x];
    }
    if (ans == inf) {
        ans = -1;
    }
    return ans;
}

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