oj.uz

Submission #441445

# Submission time Handle Problem Language Result Execution time Memory
441445 2021-07-05T08:09:22 Z colossal_pepe Birmingham (COCI20_birmingham) C++17
70 / 70
 228 ms 8312 KB 
#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.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 7984 KB Output is correct
2 Correct 178 ms 8224 KB Output is correct
3 Correct 228 ms 8260 KB Output is correct
4 Correct 150 ms 7740 KB Output is correct
5 Correct 151 ms 7828 KB Output is correct
6 Correct 195 ms 8224 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 8260 KB Output is correct
2 Correct 192 ms 8124 KB Output is correct
3 Correct 207 ms 8240 KB Output is correct
4 Correct 188 ms 8260 KB Output is correct
5 Correct 176 ms 8180 KB Output is correct
6 Correct 205 ms 7860 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 8016 KB Output is correct
2 Correct 197 ms 8280 KB Output is correct
3 Correct 192 ms 8260 KB Output is correct
4 Correct 181 ms 8312 KB Output is correct
5 Correct 188 ms 8072 KB Output is correct
6 Correct 174 ms 7948 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 7876 KB Output is correct
2 Correct 181 ms 8184 KB Output is correct
3 Correct 179 ms 8260 KB Output is correct
4 Correct 165 ms 8004 KB Output is correct
5 Correct 156 ms 7880 KB Output is correct
6 Correct 172 ms 7804 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 7876 KB Output is correct
2 Correct 172 ms 8156 KB Output is correct
3 Correct 174 ms 7876 KB Output is correct
4 Correct 167 ms 7908 KB Output is correct
5 Correct 169 ms 8064 KB Output is correct
6 Correct 168 ms 7868 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 7792 KB Output is correct
2 Correct 171 ms 8004 KB Output is correct
3 Correct 163 ms 7816 KB Output is correct
4 Correct 204 ms 8148 KB Output is correct
5 Correct 153 ms 7876 KB Output is correct
6 Correct 172 ms 7988 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 8024 KB Output is correct
2 Correct 145 ms 7776 KB Output is correct
3 Correct 205 ms 8224 KB Output is correct
4 Correct 158 ms 8004 KB Output is correct
5 Correct 169 ms 8044 KB Output is correct
6 Correct 202 ms 8244 KB Output is correct