oj.uz

Submission #733475

# Submission time Handle Problem Language Result Execution time Memory
733475 2023-04-30T21:55:51 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 104 ms 17208 KB 
// author: MisterReaper (Ahmet Alp Orakci)
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e5 + 5;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #include "debug.h"
    #define OPEN freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    #define TIME cerr << "\n" << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds ";
#else
    #define debug(...) void(23)
    #define OPEN void(0000)
    #define TIME void(232323233)
#endif

vector <int> graph[MAXN];
int ans[MAXN];

void solve()
{
    memset(ans, -1, sizeof(ans));

    int n, m, q, k; cin >> n >> m >> q >> k;
    int arr[q];
    for(int &i : arr) cin >> i;

    vector <int> vec;
    vec.emplace_back(0);
    for(int i = 1; vec.back() <= n; i++) vec.emplace_back(vec.back() + k * i);

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

        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
    }

    queue <pair <int, int>> que;
    for(int i : arr) que.emplace(i, 0);

    while(!que.empty())
    {
        auto [node, cost] = que.front();
        que.pop();
        if(ans[node] != -1) continue;
        ans[node] = cost;

        for(int child : graph[node])
        {
            que.emplace(child, cost +1);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        debug(ans[i]);
        int ret = upper_bound(vec.begin(), vec.end(), ans[i] -1) - vec.begin();
        cout << ret << " ";
    }
    
    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }

    TIME;

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13376 KB Output is correct
2 Correct 83 ms 14672 KB Output is correct
3 Correct 90 ms 16472 KB Output is correct
4 Correct 64 ms 12284 KB Output is correct
5 Correct 79 ms 12672 KB Output is correct
6 Correct 92 ms 17208 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 14700 KB Output is correct
2 Correct 91 ms 14068 KB Output is correct
3 Correct 85 ms 15464 KB Output is correct
4 Correct 97 ms 15128 KB Output is correct
5 Correct 86 ms 14284 KB Output is correct
6 Correct 86 ms 15548 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13808 KB Output is correct
2 Correct 83 ms 14748 KB Output is correct
3 Correct 87 ms 16204 KB Output is correct
4 Correct 93 ms 14828 KB Output is correct
5 Correct 72 ms 13152 KB Output is correct
6 Correct 84 ms 15812 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12812 KB Output is correct
2 Correct 87 ms 14128 KB Output is correct
3 Correct 104 ms 15656 KB Output is correct
4 Correct 78 ms 13580 KB Output is correct
5 Correct 74 ms 12712 KB Output is correct
6 Correct 90 ms 15256 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12640 KB Output is correct
2 Correct 83 ms 13520 KB Output is correct
3 Correct 76 ms 14140 KB Output is correct
4 Correct 69 ms 13144 KB Output is correct
5 Correct 83 ms 13508 KB Output is correct
6 Correct 75 ms 15064 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12784 KB Output is correct
2 Correct 97 ms 13692 KB Output is correct
3 Correct 81 ms 14344 KB Output is correct
4 Correct 87 ms 14028 KB Output is correct
5 Correct 87 ms 13056 KB Output is correct
6 Correct 81 ms 15616 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13244 KB Output is correct
2 Correct 68 ms 12484 KB Output is correct
3 Correct 91 ms 16344 KB Output is correct
4 Correct 79 ms 13252 KB Output is correct
5 Correct 82 ms 13664 KB Output is correct
6 Correct 92 ms 17088 KB Output is correct