Submission #520244

#	Time	Username	Problem	Language	Result	Execution time	Memory
520244		KoD	Birmingham (COCI20_birmingham)	C++17	70 / 70	106 ms	10564 KiB

birmingham

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5