Submission #238354

#	Time	Username	Problem	Language	Result	Execution time	Memory
238354		danikoynov	Birmingham (COCI20_birmingham)	C++14	70 / 70	122 ms	14556 KiB

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5