oj.uz

Submission #559421

# Submission time Handle Problem Language Result Execution time Memory
559421 2022-05-09T18:10:02 Z kappa Birmingham (COCI20_birmingham) C++14
25 / 70
 189 ms 18444 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], ans[maxn];

vector<ll> v[maxn];

int main(){
    cin >> n >> m >> qu >> k;
    memset(ans, -1, sizeof(ans));
    queue<piiq> q;
    for (int i = 0; i < qu; i++)
    {
        ll a;
        cin >> a;
        q.push({{a, 0}, 1});
        ans[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()){
        piiq curr = q.front();
        ll index = curr.st.st, dis = curr.st.nd, day = curr.nd;
        q.pop();

        if(vis[index]){
            continue;;
        }
        vis[index] = 1;

        if(dis > k){
            dis = 0;
            day++;
        }

        if(ans[index] == -1){
            ans[index] = day;
        }

        for (int i = 0; i < v[index].size(); i++)
        {
            ll next = v[index][i];
            q.push({{next, dis + 1}, day});
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
}

Compilation message

birmingham.cpp: In function 'int main()':
birmingham.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < v[index].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 4 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6548 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 4 ms 6484 KB Output is correct
2 Correct 4 ms 6548 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 16416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 17648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 16624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 15728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 15736 KB Output is correct
2 Incorrect 148 ms 18444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 15836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 16308 KB Output isn't correct
2 Halted 0 ms 0 KB -