oj.uz

Submission #845246

# Submission time Handle Problem Language Result Execution time Memory
845246 2023-09-06T12:48:13 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 122 ms 8904 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

constexpr static int MXN = 1e5;

int n, m, k, q;
bitset<MXN> visited;

vector<int> g[MXN];
vector<int> v;
int vv[MXN];
int res[MXN];

int main()
{
	cin >> n >> m >> q >> k;
	for (int i = 0; i < q; i++)
	{
		int val;
		cin >> val;
		v.pb(val-1);
	}
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		a--,b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	for (int i : v)
		visited[i] = true;
	int j = 1;
	while (!v.empty())
	{
		queue<array<int, 2>> t;
		for (int i : v)
			t.push({i, j*k});
		v.clear();
		while (t.size())
		{
			auto [node, s] = t.front();
			t.pop();
			if (s != j*k)
				res[node] = j;
			if (s == 0)
			{
				v.pb(node);
				continue;
			}
			for (int c : g[node])
			{
				if (!visited[c])
				{
					t.push({c, s-1});
					visited[c] = true;
				}
			}
		}
		j++;
	}
	for (int i = 0; i < n; i++)
		cout << res[i] << " ";
	cout << "\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 8020 KB Output is correct
2 Correct 104 ms 8200 KB Output is correct
3 Correct 111 ms 8508 KB Output is correct
4 Correct 98 ms 7920 KB Output is correct
5 Correct 89 ms 7812 KB Output is correct
6 Correct 110 ms 8664 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 8276 KB Output is correct
2 Correct 99 ms 8204 KB Output is correct
3 Correct 104 ms 8400 KB Output is correct
4 Correct 104 ms 8296 KB Output is correct
5 Correct 99 ms 8196 KB Output is correct
6 Correct 96 ms 8396 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8144 KB Output is correct
2 Correct 104 ms 8308 KB Output is correct
3 Correct 110 ms 8396 KB Output is correct
4 Correct 105 ms 8492 KB Output is correct
5 Correct 106 ms 8020 KB Output is correct
6 Correct 105 ms 8368 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 7748 KB Output is correct
2 Correct 96 ms 8132 KB Output is correct
3 Correct 118 ms 8476 KB Output is correct
4 Correct 90 ms 7860 KB Output is correct
5 Correct 85 ms 7728 KB Output is correct
6 Correct 95 ms 8404 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8300 KB Output is correct
2 Correct 93 ms 8268 KB Output is correct
3 Correct 95 ms 8420 KB Output is correct
4 Correct 105 ms 7860 KB Output is correct
5 Correct 92 ms 8276 KB Output is correct
6 Correct 93 ms 7960 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7784 KB Output is correct
2 Correct 101 ms 8284 KB Output is correct
3 Correct 97 ms 8132 KB Output is correct
4 Correct 110 ms 8456 KB Output is correct
5 Correct 92 ms 7968 KB Output is correct
6 Correct 99 ms 8332 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 7908 KB Output is correct
2 Correct 84 ms 8016 KB Output is correct
3 Correct 108 ms 8396 KB Output is correct
4 Correct 91 ms 8016 KB Output is correct
5 Correct 96 ms 7988 KB Output is correct
6 Correct 122 ms 8904 KB Output is correct