Submission #845084

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
845084	2023-09-06T11:53:23 Z	vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	125 ms	21488 KB

birmingham

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n,m,q,k,vis[N],ans[N];
vector < int > graph[N];
queue < pair < int , int > > bfs;
void solve(){
	cin >> n >> m >> q >> k;
	memset(vis , 0 , sizeof(vis));
	for(int i = 0;i<q;i++){
		int u;cin >> u;
		bfs.push({u,0});
	}
	for(int i = 0;i<m;i++){
		int u,v;cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	map < int , int > bruh;
	bruh[0] = 0;
	int last = 0;
	for(int i = 1;i<=n;i++){
		for(int j = last+1;j <= (last + i * k);j++)bruh[j] = i;
		last += i * k;
		if(last > n)break;
	}
	while(bfs.size()){
		int node = bfs.front().first , dist = bfs.front().second;
		bfs.pop();
		if(vis[node])continue;
		vis[node] = 1;
		ans[node] = bruh[dist];
		for(auto itr : graph[node]){
			bfs.push({itr,dist+1});
		}
	}
	for(int i = 1;i<=n;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3160 KB	Output is correct
2	Correct	1 ms	3160 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	3216 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	3164 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct
3	Correct	1 ms	3164 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	3164 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	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
4	Correct	2 ms	3164 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	13448 KB	Output is correct
2	Correct	83 ms	13696 KB	Output is correct
3	Correct	100 ms	14500 KB	Output is correct
4	Correct	75 ms	13036 KB	Output is correct
5	Correct	107 ms	19112 KB	Output is correct
6	Correct	97 ms	14964 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	13780 KB	Output is correct
2	Correct	72 ms	13860 KB	Output is correct
3	Correct	75 ms	14072 KB	Output is correct
4	Correct	106 ms	13904 KB	Output is correct
5	Correct	104 ms	16464 KB	Output is correct
6	Correct	99 ms	14104 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	13580 KB	Output is correct
2	Correct	105 ms	13788 KB	Output is correct
3	Correct	73 ms	14416 KB	Output is correct
4	Correct	110 ms	13920 KB	Output is correct
5	Correct	93 ms	16152 KB	Output is correct
6	Correct	65 ms	13908 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	13136 KB	Output is correct
2	Correct	68 ms	13816 KB	Output is correct
3	Correct	116 ms	14492 KB	Output is correct
4	Correct	65 ms	13396 KB	Output is correct
5	Correct	89 ms	17724 KB	Output is correct
6	Correct	85 ms	13904 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	13196 KB	Output is correct
2	Correct	91 ms	13424 KB	Output is correct
3	Correct	78 ms	13668 KB	Output is correct
4	Correct	71 ms	13220 KB	Output is correct
5	Correct	95 ms	21488 KB	Output is correct
6	Correct	89 ms	13656 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	13192 KB	Output is correct
2	Correct	65 ms	13392 KB	Output is correct
3	Correct	125 ms	13652 KB	Output is correct
4	Correct	98 ms	13652 KB	Output is correct
5	Correct	114 ms	18232 KB	Output is correct
6	Correct	80 ms	14140 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	13336 KB	Output is correct
2	Correct	67 ms	13020 KB	Output is correct
3	Correct	86 ms	14400 KB	Output is correct
4	Correct	77 ms	13396 KB	Output is correct
5	Correct	82 ms	17288 KB	Output is correct
6	Correct	75 ms	14676 KB	Output is correct

Submission #845084

Compilation message