oj.uz

답안 #238354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238354 2020-06-10T20:44:19 Z danikoynov Birmingham (COCI20_birmingham) C++14
70 / 70
 122 ms 14556 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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