Submission #1029939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029939		VMaksimoski008	Swapping Cities (APIO20_swap)	C++17	37 / 100	2056 ms	13648 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using Edge = array<int, 3>;

const int maxn = 1e5 + 5;

struct DSU {
    int n;
    vector<int> par, size;

    DSU(int _n) {
        n = _n + 1;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool uni(int a, int b) {
        a = find(a), b = find(b);
        if(a == b) return 0;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
        return 1;
    }

    bool same_set(int a, int b) { return find(a) == find(b); }
};

int n, m;
vector<Edge> edges;

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.push_back({ U[i], V[i], W[i] });
    sort(edges.begin(), edges.end(), [&](Edge &a, Edge &b) { return a[2] < b[2]; });
}

int getMinimumFuelCapacity(int X, int Y) {
    int l=2, r=m-1, ans=-1;

    while(l <= r) {
        int mid = (l + r) / 2;
        DSU dsu(n);

        vector<int> deg(n);

        for(int i=0; i<=mid; i++) {
            dsu.uni(edges[i][0], edges[i][1]);
            deg[edges[i][0]]++; deg[edges[i][1]]++;
        }

        bool line = false;
        vector<int> cnt(n);
        int mx = 0;

        for(int i=0; i<n; i++) {
            if(dsu.find(i) != dsu.find(X)) continue;
            cnt[deg[i]]++;
            mx = max(mx, deg[i]);
        }

        if(mx <= 2 && cnt[1] == 2) line = 1;

        if(dsu.same_set(X, Y) && !line) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    return (ans == -1 ? ans : edges[ans][2]);
}

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