oj.uz

답안 #402061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402061 2021-05-11T09:15:47 Z KoD 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -