oj.uz

Submission #440528

# Submission time Handle Problem Language Result Execution time Memory
440528 2021-07-02T11:28:58 Z Abrar_Al_Samit Birmingham (COCI20_birmingham) C++17
70 / 70
 116 ms 8256 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int maxn = 1e5 + 5;
vector<int>g[maxn];
void PlayGround() {
    int n, m, q, k; cin >> n >> m >> q >> k;

    queue<pair<pair<int,int>,int>>qq;
    vector<int>ans(n+1, -1);
    for(int i=0; i<q; ++i) {
        int x; cin >> x;
        qq.push(make_pair(make_pair(x, 0), 1));
        ans[x] = 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(!qq.empty()) {
        int node = qq.front().first.first;
        int dis = qq.front().first.second;
        int day = qq.front().second;
        qq.pop();
        ++dis;
        if(day * k < dis) {
            ++day;
            dis = 1;
        }
        for(int to : g[node]) {
            if(ans[to]==-1) {
                ans[to] = day;
                qq.push(make_pair(make_pair(to, dis), day));
            }
        }
    }
    for(int i=1; i<=n; ++i) {
        assert(ans[i]!=-1);
        cout << ans[i] << ' ';
    }
    cout << '\n';
    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
} 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    // #endif
    PlayGround();

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7668 KB Output is correct
2 Correct 115 ms 7920 KB Output is correct
3 Correct 92 ms 8216 KB Output is correct
4 Correct 86 ms 7380 KB Output is correct
5 Correct 87 ms 7552 KB Output is correct
6 Correct 101 ms 8256 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 7936 KB Output is correct
2 Correct 94 ms 7824 KB Output is correct
3 Correct 98 ms 7924 KB Output is correct
4 Correct 95 ms 8004 KB Output is correct
5 Correct 103 ms 7852 KB Output is correct
6 Correct 86 ms 7992 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7752 KB Output is correct
2 Correct 114 ms 7992 KB Output is correct
3 Correct 103 ms 8188 KB Output is correct
4 Correct 105 ms 8008 KB Output is correct
5 Correct 85 ms 7632 KB Output is correct
6 Correct 87 ms 7948 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7492 KB Output is correct
2 Correct 102 ms 7836 KB Output is correct
3 Correct 88 ms 7916 KB Output is correct
4 Correct 93 ms 7620 KB Output is correct
5 Correct 99 ms 7424 KB Output is correct
6 Correct 84 ms 7808 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7484 KB Output is correct
2 Correct 96 ms 7736 KB Output is correct
3 Correct 87 ms 7712 KB Output is correct
4 Correct 80 ms 7712 KB Output is correct
5 Correct 84 ms 7696 KB Output is correct
6 Correct 84 ms 7804 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7492 KB Output is correct
2 Correct 88 ms 7728 KB Output is correct
3 Correct 93 ms 7748 KB Output is correct
4 Correct 93 ms 7876 KB Output is correct
5 Correct 91 ms 7524 KB Output is correct
6 Correct 91 ms 7892 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 7620 KB Output is correct
2 Correct 87 ms 7440 KB Output is correct
3 Correct 96 ms 8060 KB Output is correct
4 Correct 89 ms 7620 KB Output is correct
5 Correct 98 ms 7712 KB Output is correct
6 Correct 89 ms 8200 KB Output is correct