Submission #369394

#	Time	Username	Problem	Language	Result	Execution time	Memory
369394		Falcon	Swapping Cities (APIO20_swap)	C++17	100 / 100	370 ms	12780 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int INF{1 << 30};

vector<int> p, p_w, sz, l_w;

int find(int i, int w) {
    while(p_w[i] <= w) i = p[i];
    return i;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    
    p = vector<int>(N), iota(p.begin(), p.end(), 0);
    p_w = vector<int>(N, INF); 
    sz = vector<int>(N, 1), l_w = vector<int>(N, INF);

    vector<int> ord(M); iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return tie(W[i], i) < tie(W[j], j); });

    vector<int> d(N);
    for(int i : ord) {
        int u = find(U[i], W[i]), v = find(V[i], W[i]);
        ++d[U[i]], ++d[V[i]];

        if(u == v) {
            l_w[u] = min(W[i], l_w[u]);
            continue;
        }

        if(sz[v] < sz[u])
            swap(u, v);

        p[u] = v;
        sz[v] += sz[u];
        p_w[u] = W[i];

        if(l_w[v] <= W[i])
            continue;
        else if(l_w[u] <= W[i])
            l_w[v] = W[i];
        else if(d[U[i]] > 2 || d[V[i]] > 2)
            l_w[v] = W[i];
        
    }
}

int getMinimumFuelCapacity(int x, int y) {
    auto check = [&](int w) {
        int u = find(x, w), v = find(y, w);
        return u == v && l_w[u] <= w;
    };

    if(!check(INF - 1))
        return -1;
    
    int w{0};
    for(int t{INF >> 1}; t > 0; t >>= 1)
        if(!check(w + t))
            w += t;

    return w + 1;
}

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