Submission #238354

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
238354	2020-06-10T20:44:19 Z	danikoynov	Birmingham (COCI20_birmingham)	C++14	70 / 70	122 ms	14556 KB

birmingham

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int MAXN = (1 << 18);

vector < int > v[MAXN];
int n, m, q, k, d[MAXN], s[MAXN], used[MAXN];
void read()
{
    cin >> n >> m >> q >> k;

    for (int i = 1; i <= q; i ++)
        cin >> s[i];

    int a, b;
    for (int i = 0; i < m; i ++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}

void bfs()
{
    queue < int > qt;
    for (int i = 1; i <= q; i ++)
        qt.push(s[i]), used[s[i]] = 1;

    while(!qt.empty())
    {
        int cur = qt.front(), sz = v[cur].size();
        qt.pop();
        for (int i = 0; i < sz; i ++)
        {
            int next = v[cur][i];
            if (!used[next])
            {
                used[next] = used[cur] + 1;
                qt.push(next);
            }
        }
    }
}

void fill_array()
{
    int id = 1, step = 1;
    while(id <= n)
    {
        int r = id + step * k - 1;
        if (n < r)
            r = n;

        for (int i = id; i <= r; i ++)
            d[i] = step;

        id = r + 1;
        step ++;
    }
}

void solve()
{
    read();
    bfs();
    fill_array();
    for (int i = 1; i <= n; i ++)
    {
        int x = used[i] - 1;
        cout << d[x] << " ";
    }
    cout << endl;
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
    return 0;
}
/**
7 8 1 1
2
1 2
2 3
3 4
1 4
4 7
7 5
5 6
6 3
*/

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6528 KB	Output is correct
2	Correct	8 ms	6528 KB	Output is correct
3	Correct	9 ms	6560 KB	Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6528 KB	Output is correct
2	Correct	8 ms	6528 KB	Output is correct
3	Correct	8 ms	6528 KB	Output is correct
4	Correct	10 ms	6528 KB	Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	11612 KB	Output is correct
2	Correct	109 ms	14028 KB	Output is correct
3	Correct	122 ms	14556 KB	Output is correct
4	Correct	84 ms	13168 KB	Output is correct
5	Correct	96 ms	13416 KB	Output is correct
6	Correct	104 ms	14516 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	11856 KB	Output is correct
2	Correct	101 ms	14036 KB	Output is correct
3	Correct	106 ms	14248 KB	Output is correct
4	Correct	111 ms	14156 KB	Output is correct
5	Correct	103 ms	13908 KB	Output is correct
6	Correct	112 ms	13868 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	11736 KB	Output is correct
2	Correct	111 ms	14156 KB	Output is correct
3	Correct	111 ms	14480 KB	Output is correct
4	Correct	110 ms	14156 KB	Output is correct
5	Correct	90 ms	13536 KB	Output is correct
6	Correct	92 ms	14008 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	11516 KB	Output is correct
2	Correct	101 ms	14040 KB	Output is correct
3	Correct	105 ms	14248 KB	Output is correct
4	Correct	91 ms	13660 KB	Output is correct
5	Correct	91 ms	13288 KB	Output is correct
6	Correct	98 ms	13884 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	11464 KB	Output is correct
2	Correct	95 ms	13660 KB	Output is correct
3	Correct	92 ms	13752 KB	Output is correct
4	Correct	96 ms	13536 KB	Output is correct
5	Correct	92 ms	13712 KB	Output is correct
6	Correct	90 ms	14012 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	11524 KB	Output is correct
2	Correct	95 ms	13656 KB	Output is correct
3	Correct	93 ms	13812 KB	Output is correct
4	Correct	98 ms	13908 KB	Output is correct
5	Correct	95 ms	13500 KB	Output is correct
6	Correct	91 ms	14008 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	11616 KB	Output is correct
2	Correct	85 ms	13164 KB	Output is correct
3	Correct	103 ms	14488 KB	Output is correct
4	Correct	94 ms	13540 KB	Output is correct
5	Correct	97 ms	13708 KB	Output is correct
6	Correct	103 ms	14520 KB	Output is correct

Submission #238354

Compilation message