oj.uz

Submission #402061

# Submission time Handle Problem Language Result Execution time Memory
402061 2021-05-11T09:15:47 Z KoD Swapping Cities (APIO20_swap) C++17
6 / 100
 259 ms 12196 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);
    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) {
        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) {
                date[u] = W[i];
            }
            if (date[v] == INF and date[u] != INF) {
                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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 2 ms 300 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 44 ms 5572 KB Output is correct
10 Correct 55 ms 6780 KB Output is correct
11 Correct 57 ms 6728 KB Output is correct
12 Correct 54 ms 7068 KB Output is correct
13 Correct 51 ms 7108 KB Output is correct
14 Correct 62 ms 5920 KB Output is correct
15 Correct 241 ms 10624 KB Output is correct
16 Correct 241 ms 10436 KB Output is correct
17 Correct 259 ms 11044 KB Output is correct
18 Correct 146 ms 10920 KB Output is correct
19 Correct 125 ms 6464 KB Output is correct
20 Correct 231 ms 11580 KB Output is correct
21 Correct 235 ms 11716 KB Output is correct
22 Correct 243 ms 12148 KB Output is correct
23 Correct 151 ms 12196 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 135 ms 9964 KB Output isn't correct
4 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 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 2 ms 300 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Incorrect 2 ms 332 KB Output isn't correct
11 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 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 2 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 44 ms 5572 KB Output is correct
11 Correct 55 ms 6780 KB Output is correct
12 Correct 57 ms 6728 KB Output is correct
13 Correct 54 ms 7068 KB Output is correct
14 Correct 51 ms 7108 KB Output is correct
15 Incorrect 2 ms 332 KB Output isn't correct
16 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 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 2 ms 300 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 44 ms 5572 KB Output is correct
10 Correct 55 ms 6780 KB Output is correct
11 Correct 57 ms 6728 KB Output is correct
12 Correct 54 ms 7068 KB Output is correct
13 Correct 51 ms 7108 KB Output is correct
14 Correct 62 ms 5920 KB Output is correct
15 Correct 241 ms 10624 KB Output is correct
16 Correct 241 ms 10436 KB Output is correct
17 Correct 259 ms 11044 KB Output is correct
18 Correct 146 ms 10920 KB Output is correct
19 Incorrect 135 ms 9964 KB Output isn't correct
20 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 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 2 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 44 ms 5572 KB Output is correct
11 Correct 55 ms 6780 KB Output is correct
12 Correct 57 ms 6728 KB Output is correct
13 Correct 54 ms 7068 KB Output is correct
14 Correct 51 ms 7108 KB Output is correct
15 Correct 62 ms 5920 KB Output is correct
16 Correct 241 ms 10624 KB Output is correct
17 Correct 241 ms 10436 KB Output is correct
18 Correct 259 ms 11044 KB Output is correct
19 Correct 146 ms 10920 KB Output is correct
20 Incorrect 135 ms 9964 KB Output isn't correct
21 Halted 0 ms 0 KB -