oj.uz

Submission #520244

# Submission time Handle Problem Language Result Execution time Memory
520244 2022-01-29T02:09:20 Z KoD Birmingham (COCI20_birmingham) C++17
70 / 70
 106 ms 10564 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, Q, K;
    std::cin >> N >> M >> Q >> K;
    vector<int> dist(N, -1);
    std::queue<int> que;
    const auto push = [&](const int u, const int d) {
        if (dist[u] == -1) {
            dist[u] = d;
            que.push(u);
        }
    };
    while (Q--) {
        int u;
        std::cin >> u;
        push(u - 1, 0);
    }
    vector<vector<int>> graph(N);
    while (M--) {
        int a, b;
        std::cin >> a >> b;
        a -= 1, b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    while (!que.empty()) {
        const int u = que.front();
        que.pop();
        for (const int v : graph[u]) {
            push(v, dist[u] + 1);
        }
    }
    vector<int> time(N);
    for (int l = 1, k = 1; l < N; ++k) {
        const int r = std::min(N, l + k * K);
        for (int i = l; i < r; ++i) {
            time[i] = k;
        }
        l = r;
    }
    for (int i = 0; i < N; ++i) {
        std::cout << time[dist[i]] << " \n"[i + 1 == N];
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 208 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9732 KB Output is correct
2 Correct 86 ms 10200 KB Output is correct
3 Correct 75 ms 10556 KB Output is correct
4 Correct 60 ms 9220 KB Output is correct
5 Correct 66 ms 9496 KB Output is correct
6 Correct 91 ms 10552 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10264 KB Output is correct
2 Correct 81 ms 10076 KB Output is correct
3 Correct 93 ms 10336 KB Output is correct
4 Correct 91 ms 10272 KB Output is correct
5 Correct 100 ms 10136 KB Output is correct
6 Correct 75 ms 9800 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9780 KB Output is correct
2 Correct 95 ms 10436 KB Output is correct
3 Correct 74 ms 10564 KB Output is correct
4 Correct 76 ms 10300 KB Output is correct
5 Correct 78 ms 9600 KB Output is correct
6 Correct 74 ms 10000 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9380 KB Output is correct
2 Correct 70 ms 10056 KB Output is correct
3 Correct 75 ms 10360 KB Output is correct
4 Correct 81 ms 9792 KB Output is correct
5 Correct 66 ms 9380 KB Output is correct
6 Correct 76 ms 9812 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 9384 KB Output is correct
2 Correct 82 ms 9796 KB Output is correct
3 Correct 74 ms 9732 KB Output is correct
4 Correct 82 ms 9660 KB Output is correct
5 Correct 71 ms 9800 KB Output is correct
6 Correct 93 ms 9792 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9524 KB Output is correct
2 Correct 77 ms 9856 KB Output is correct
3 Correct 58 ms 9692 KB Output is correct
4 Correct 79 ms 10060 KB Output is correct
5 Correct 80 ms 9616 KB Output is correct
6 Correct 72 ms 10020 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9672 KB Output is correct
2 Correct 61 ms 9416 KB Output is correct
3 Correct 90 ms 10404 KB Output is correct
4 Correct 62 ms 9636 KB Output is correct
5 Correct 85 ms 9872 KB Output is correct
6 Correct 86 ms 10560 KB Output is correct