Submission #441445

#	Time	Username	Problem	Language	Result	Execution time	Memory
441445		colossal_pepe	Birmingham (COCI20_birmingham)	C++17	70 / 70	228 ms	8312 KiB

birmingham

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1000000000;

int n, m, q, k, u, v, dist[100005];
vector<vector<int>> graph;
queue<int> bfs_q;

void setup() {
    for (int i = 0; i < 100005; i++) {
        dist[i] = INF;
    }
}

void fillDist() {
    while (not bfs_q.empty()) {
        int node = bfs_q.front();
        bfs_q.pop();
        for (int adj: graph[node]) {
            if (dist[adj] == INF) {
                dist[adj] = dist[node] + 1;
                bfs_q.push(adj);
            }
        }
    }
}

int getDay(long long distance) {
    long long day = 0;
    while (k*((day*(day+1))/2) < distance) {
        day++;
    }
    return day;
}

int main() {
    setup();
    cin >> n >> m >> q >> k;
    graph.resize(n);
    for (int i = 0; i < q; i++) {
        cin >> u;
        dist[u - 1] = 0;
        bfs_q.push(u - 1);
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        graph[u - 1].push_back(v - 1);
        graph[v - 1].push_back(u - 1);
    }
    fillDist();
    for (int i = 0; i < n; i++) {
        cout << getDay(dist[i]) << ' ';
    }
    cout << endl;
    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