oj.uz

Submission #559436

# Submission time Handle Problem Language Result Execution time Memory
559436 2022-05-09T18:54:08 Z kappa Birmingham (COCI20_birmingham) C++14
70 / 70
 207 ms 20652 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define MOD 1000000007
typedef pair<ll, ll> pii;
typedef pair<pii, ll> piiq;

const ll maxn = 2e5 + 5;

ll n, m, qu, k, vis[maxn], dis[maxn], ans[maxn];

vector<ll> v[maxn];

int main(){
    cin >> n >> m >> qu >> k;
    queue<pii> q;
    for (int i = 0; i < qu; i++)
    {
        ll a;
        cin >> a;
        q.push({a, 0});
    }
    for (int i = 0; i < m; i++)
    {
        ll y, u;
        cin >> y >> u;
        v[y].pb(u);
        v[u].pb(y);
    }

    while(!q.empty()){
        pii curr = q.front();
        q.pop();

        if(vis[curr.st]){
            continue;
        }
        vis[curr.st] = 1;

        dis[curr.st] = curr.nd;

        for (int i = 0; i < v[curr.st].size(); i++)
        {
            ll next = v[curr.st][i];
            q.push({next, curr.nd + 1});
        }
    }

    ll pt = 1, j = 1;
    while (pt < maxn) {
        for(int i = pt; i <= pt + j * k; i++) {
            if (i < maxn) ans[i] = j;
        }
        pt += j * k;
        j++;
    }

    for (int i = 1; i <= n; i++)
    {
        cout << ans[dis[i]] << " ";
    }
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < v[curr.st].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6544 KB Output is correct
3 Correct 4 ms 6552 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 15964 KB Output is correct
2 Correct 158 ms 19344 KB Output is correct
3 Correct 186 ms 19192 KB Output is correct
4 Correct 143 ms 16972 KB Output is correct
5 Correct 133 ms 17152 KB Output is correct
6 Correct 177 ms 20440 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 17080 KB Output is correct
2 Correct 163 ms 18424 KB Output is correct
3 Correct 177 ms 19388 KB Output is correct
4 Correct 175 ms 19624 KB Output is correct
5 Correct 149 ms 19092 KB Output is correct
6 Correct 161 ms 18064 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 16612 KB Output is correct
2 Correct 159 ms 19024 KB Output is correct
3 Correct 191 ms 19620 KB Output is correct
4 Correct 161 ms 19452 KB Output is correct
5 Correct 141 ms 17684 KB Output is correct
6 Correct 144 ms 19804 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 15576 KB Output is correct
2 Correct 149 ms 18912 KB Output is correct
3 Correct 156 ms 19836 KB Output is correct
4 Correct 141 ms 18212 KB Output is correct
5 Correct 129 ms 17368 KB Output is correct
6 Correct 146 ms 19192 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 15300 KB Output is correct
2 Correct 144 ms 15976 KB Output is correct
3 Correct 145 ms 18516 KB Output is correct
4 Correct 134 ms 17740 KB Output is correct
5 Correct 140 ms 18304 KB Output is correct
6 Correct 143 ms 18456 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 15672 KB Output is correct
2 Correct 138 ms 18336 KB Output is correct
3 Correct 135 ms 18564 KB Output is correct
4 Correct 161 ms 18388 KB Output is correct
5 Correct 156 ms 17788 KB Output is correct
6 Correct 149 ms 18220 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 16072 KB Output is correct
2 Correct 128 ms 17196 KB Output is correct
3 Correct 170 ms 20652 KB Output is correct
4 Correct 133 ms 17940 KB Output is correct
5 Correct 144 ms 18464 KB Output is correct
6 Correct 165 ms 19628 KB Output is correct