Submission #714920

#	Time	Username	Problem	Language	Result	Execution time	Memory
714920		dxz05	Swapping Cities (APIO20_swap)	C++17	37 / 100	2064 ms	8160 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 100005;
vector<tuple<int, int, int>> edges;

int N, M;

int parent[MaxN];
bool line[MaxN];
pair<int, int> tail[MaxN];

void make_set(int i){
    parent[i] = i;
    line[i] = true;
    tail[i] = make_pair(i, i);
}

int leader(int x){
    return parent[x] == x ? x : parent[x] = leader(parent[x]);
}

void unite(int x, int y){
    int X = x, Y = y;
    x = leader(x);
    y = leader(y);

    if (x == y){
        line[y] = false;
        return;
    }

    parent[x] = y;
    if (!line[x]){
        line[y] = false;
        return;
    }

    if (!line[y]) return;

    if (tail[x].first != X && tail[x].second != X){
        line[y] = false;
        return;
    }

    if (tail[y].first != Y && tail[y].second != Y){
        line[y] = false;
        return;
    }

    pair<int, int> new_tail;
    new_tail.first = tail[x].first ^ tail[x].second ^ X;
    new_tail.second = tail[y].first ^ tail[y].second ^ Y;

    tail[y] = new_tail;
}

bool can(int x, int y){
    x = leader(x);
    y = leader(y);
    return x == y && !line[x];
}

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(edges.begin(), edges.end());
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 0; i < N; i++) make_set(i);

    for (auto [w, u, v] : edges){
        unite(u, v);
        if (can(X, Y)) return 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