oj.uz

Submission #998998

# Submission time Handle Problem Language Result Execution time Memory
998998 2024-06-15T04:04:38 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 180 ms 12884 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, m, p, k, dist[N];
queue<int> q;
vector<int> g[N];

int main(){
    memset(dist, 31, sizeof dist);

    cin >> n >> m >> p >> k;
    for (int i = 0; i < p; i ++){
        int v;
        cin >> v;

        q.push(v);
        dist[v] = 0;
    }

    for (int i = 0; i < m; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int u : g[v]){
            if (dist[u] > dist[v] + 1){
                q.push(u);
                dist[u] = dist[v] + 1;
            }
        }
    }

    for (int i = 1; i <= n; i ++){
        int sm = 0;
        for (int x = 0; x <= n; x ++){
            sm += (x * k);
            if (dist[i] <= sm){
                cout << x << " ";
                break;
            }
        }
    }
    cout << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11860 KB Output is correct
2 Correct 89 ms 12372 KB Output is correct
3 Correct 96 ms 12884 KB Output is correct
4 Correct 70 ms 11348 KB Output is correct
5 Correct 73 ms 11860 KB Output is correct
6 Correct 94 ms 12812 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 12548 KB Output is correct
2 Correct 84 ms 12368 KB Output is correct
3 Correct 89 ms 12368 KB Output is correct
4 Correct 91 ms 12372 KB Output is correct
5 Correct 82 ms 12368 KB Output is correct
6 Correct 115 ms 12016 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12076 KB Output is correct
2 Correct 89 ms 12372 KB Output is correct
3 Correct 94 ms 12628 KB Output is correct
4 Correct 90 ms 12368 KB Output is correct
5 Correct 84 ms 11856 KB Output is correct
6 Correct 87 ms 12116 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11860 KB Output is correct
2 Correct 82 ms 12368 KB Output is correct
3 Correct 96 ms 12576 KB Output is correct
4 Correct 83 ms 11856 KB Output is correct
5 Correct 76 ms 11796 KB Output is correct
6 Correct 89 ms 12172 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 11860 KB Output is correct
2 Correct 84 ms 11916 KB Output is correct
3 Correct 87 ms 12176 KB Output is correct
4 Correct 98 ms 11860 KB Output is correct
5 Correct 81 ms 11940 KB Output is correct
6 Correct 98 ms 12076 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 11872 KB Output is correct
2 Correct 81 ms 11860 KB Output is correct
3 Correct 85 ms 12064 KB Output is correct
4 Correct 85 ms 12368 KB Output is correct
5 Correct 82 ms 11856 KB Output is correct
6 Correct 180 ms 12112 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 11860 KB Output is correct
2 Correct 73 ms 11508 KB Output is correct
3 Correct 96 ms 12624 KB Output is correct
4 Correct 80 ms 11860 KB Output is correct
5 Correct 85 ms 12004 KB Output is correct
6 Correct 96 ms 12624 KB Output is correct