oj.uz

Submission #402065

# Submission time Handle Problem Language Result Execution time Memory
402065 2021-05-11T09:22:37 Z KoD Swapping Cities (APIO20_swap) C++17
0 / 100
 145 ms 11292 KB 
#include <bits/stdc++.h>
#include "swap.h"

template <class T>
using Vec = std::vector<T>;

constexpr int INF = 1000000000 + 5;

struct DSU {
    int cur;
    Vec<int> date, par;
    DSU() = default;
    DSU(const int n): cur(0), date(n, INF), par(n, -1) { }

    int find(int u, const int t) const {
        while (date[u] < t) u = par[u];
        return u;
    }

    void merge(int u, int v) {
        u = find(u, cur);
        v = find(v, cur);
        cur += 1;
        if (u == v) return;
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        date[v] = cur - 1;
    }

    int when(const int u, const int v) const {
        if (u == v) return 0;
        if (find(u, cur) != find(v, cur)) return INF;
        int ok = cur, ng = 0;
        while (ok - ng > 1) {
            const int md = (ok + ng) / 2;
            (find(u, md) == find(v, md) ? ok : ng) = md;
        }
        return ok;
    }
};

DSU dsu;
Vec<int> par, cost, date;

void init(int N, int M, Vec<int> U, Vec<int> V, Vec<int> W) {
    Vec<int> order(M);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](const int i, const int j) {
        return W[i] < W[j];
    });
    par = Vec<int>(N, -1);
    date = Vec<int>(N, INF);
    Vec<int> deg(N, 0);
    dsu = DSU(N);
    cost.reserve(M);
    const auto find = [&](int u) {
        while (par[u] >= 0) u = par[u];
        return u;
    };
    for (const auto i: order) {
        deg[U[i]] += 1;
        deg[V[i]] += 1;
        const bool f = U[i] > 2 or V[i] > 2;
        int u = find(U[i]);
        int v = find(V[i]);
        if (u == v) {
            if (date[u] == INF) {
                date[u] = W[i];
            }
        }
        else {
            if (par[u] > par[v]) {
                std::swap(u, v);
            }
            par[u] += par[v];
            par[v] = u;
            if (date[u] == INF and (date[v] != INF or f)) {
                date[u] = W[i];
            }
            if (date[v] == INF and (date[u] != INF or f)) {
                date[v] = W[i];
            }
        }
        dsu.merge(U[i], V[i]);
        cost.push_back(W[i]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int ret = cost[dsu.when(X, Y) - 1];
    while (par[X] >= 0 and date[X] == INF) {
        X = par[X];
    }
    while (par[Y] >= 0 and date[Y] == INF) {
        Y = par[Y];
    }
    ret = std::max(ret, std::min(date[X], date[Y]));
    return ret == INF ? -1: ret;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 143 ms 7356 KB Output is correct
4 Incorrect 145 ms 11292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -