제출 #714925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714925		dxz05	자매 도시 (APIO20_swap)	C++17	37 / 100	2068 ms	9664 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;

struct Set{
    int parent;
    bool line;
    pair<int, int> tail;
    Set(){};
    Set(int i){
        parent = i;
        line = true;
        tail = make_pair(i, i);
    }
};

Set t[MaxN];

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

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

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

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

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

    if (!t[y].line) return;

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

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

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

    t[y].tail = new_tail;
}

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

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++) t[i] = 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