제출 #1161818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161818		The_Samurai	Swapping Cities (APIO20_swap)	C++20	37 / 100	2095 ms	19132 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> p, size;

    void init(int n) {
        size.assign(n, 1);
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int a) {
        return p[a] == a ? a : p[a] = get(p[a]);
    }

    void merge(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

const int inf = 2e9;
vector<int> needs;
vector<tuple<int, int, int>> all;
int n;

void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = _n;
    needs.assign(n, inf);
    vector<pair<int, int>> vec(m);
    vector<int> cnt(n), p(n);
    vector<bool> bad(n);
    vector<vector<int>> g(n);

    for (int i = 0; i < n; i++) {
        g[i] = {i};
        p[i] = i;
    }

    for (int i = 0; i < m; i++) vec[i] = make_pair(W[i], i);
    sort(vec.begin(), vec.end());
    
    for (auto [w, i]: vec) {
        cnt[U[i]]++, cnt[V[i]]++;
        bool now = (cnt[U[i]] > 2) | (cnt[V[i]] > 2);
        int u = p[U[i]], v = p[V[i]];
        if (u == v) {
            if (bad[u]) continue;
            bad[u] = true;
            for (int x: g[u]) needs[x] = w;
            continue;
        }
        now |= bad[u] | bad[v];
        if (now and !bad[u]) {
            for (int x: g[u]) needs[x] = w;
        }
        if (now and !bad[v]) {
            for (int x: g[v]) needs[x] = w;
        }
        // cout << u << ' ' << v << ' ' << now << ' ' << w << endl;

        if (g[u].size() > g[v].size()) swap(u, v);
        for (int x: g[u]) {
            g[v].emplace_back(x);
            p[x] = v;
        }
        g[u].clear();
        bad[v] = now;
    }

    all.resize(m);
    for (int i = 0; i < m; i++) all[i] = tuple{vec[i].first, U[vec[i].second], V[vec[i].second]};
}

int getMinimumFuelCapacity(int x, int y) {
    int ans = max(needs[x], needs[y]);
    dsu ds; ds.init(n);
    for (auto [w, u, v]: all) {
        ds.merge(u, v);
        if (ds.get(x) == ds.get(y)) {
            ans = max(ans, w);
            break;
        }
    }
    return ans == inf ? -1 : 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