Submission #1190618

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

swap

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

vector<pair<int, pair<int, int>>> edge;
int N, M;

void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    for (int i = 0; i < m; i ++) {
        edge.pb({w[i], {u[i], v[i]}});
    }

    sort(edge.begin(), edge.end(), [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b){
        return a.first < b.first;
    });

    N = n;
    M = m;
}

vector<int> parent(N);
int find_parent(int v) {
    if (parent[v] == v) {return v;}
    parent[v] = find_parent(parent[v]);
    return parent[v];
}

int getMinimumFuelCapacity (int x, int y) {
    parent.clear();
    parent.resize(N);
    iota(parent.begin(), parent.end(), 0);

    vector<bool> swappable(N, false);
    vector<int> degree(N, 0);
    
    int ans = -1;
    for (int i = 0; i < M; i ++) {
        int a = edge[i].second.first, b = edge[i].second.second;
        degree[a] ++; degree[b] ++;

        if (find_parent(a) == find_parent(b)) {
            swappable[find_parent(a)] = true;
        }
        else { // not same parent => merge
            if (parent[a] > parent[b]) swap(a, b);
            if (swappable[parent[b]]) {swappable[parent[a]] = true;}
            if (degree[a] >= 3 || degree[b] >= 3) {swappable[parent[a]] = true;}

            parent[parent[b]] = parent[a];
        }

        if (find_parent(x) == find_parent(y) && swappable[parent[x]]) {
            ans = edge[i].first;
            break;
        }
    }

    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