oj.uz

Submission #845150

# Submission time Handle Problem Language Result Execution time Memory
845150 2023-09-06T12:17:12 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 63 ms 8280 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;

vector<vector<int>> graph;
int vis[MAXN], dist[MAXN];
int main() {
	fast
	int N, M, Q, K;
	cin >> N >> M >> Q >> K;

	for (int i = 1; i <= N; i++)
		dist[i] = 1e8;

	queue<int> q;
	for (int i = 0; i < Q; i++) {
		int x; cin >> x;
		q.push(x);
		dist[x] = 0;
	}

	graph = vector<vector<int>>(N+1, vector<int>());
	while (M--) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		vis[node] = true;

		for (auto u : graph[node]) {
			if (!vis[u] && dist[u] > dist[node] + 1) {
				dist[u] = dist[node] + 1;
				q.push(u);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		int now = K;
		int d = dist[i];
		while (d > 0) {
			d -= now;
			cnt++;
			now += K;
		}
		cout << cnt << " "; 
	}
	cout << "\n"; 
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7720 KB Output is correct
2 Correct 62 ms 8012 KB Output is correct
3 Correct 57 ms 8276 KB Output is correct
4 Correct 63 ms 7684 KB Output is correct
5 Correct 46 ms 7760 KB Output is correct
6 Correct 54 ms 8040 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8160 KB Output is correct
2 Correct 52 ms 7948 KB Output is correct
3 Correct 51 ms 8016 KB Output is correct
4 Correct 55 ms 8272 KB Output is correct
5 Correct 50 ms 8020 KB Output is correct
6 Correct 46 ms 7656 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7976 KB Output is correct
2 Correct 52 ms 8280 KB Output is correct
3 Correct 54 ms 8080 KB Output is correct
4 Correct 52 ms 8276 KB Output is correct
5 Correct 44 ms 7760 KB Output is correct
6 Correct 46 ms 7876 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7548 KB Output is correct
2 Correct 52 ms 8020 KB Output is correct
3 Correct 50 ms 8020 KB Output is correct
4 Correct 47 ms 7952 KB Output is correct
5 Correct 45 ms 7504 KB Output is correct
6 Correct 47 ms 7840 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7740 KB Output is correct
2 Correct 60 ms 7764 KB Output is correct
3 Correct 46 ms 7772 KB Output is correct
4 Correct 50 ms 7804 KB Output is correct
5 Correct 47 ms 7764 KB Output is correct
6 Correct 44 ms 7764 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7736 KB Output is correct
2 Correct 50 ms 7904 KB Output is correct
3 Correct 54 ms 7656 KB Output is correct
4 Correct 51 ms 8016 KB Output is correct
5 Correct 60 ms 7764 KB Output is correct
6 Correct 54 ms 7860 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7644 KB Output is correct
2 Correct 42 ms 7516 KB Output is correct
3 Correct 51 ms 8020 KB Output is correct
4 Correct 46 ms 7960 KB Output is correct
5 Correct 50 ms 8256 KB Output is correct
6 Correct 54 ms 8020 KB Output is correct