Submission #845084

#	Time	Username	Problem	Language	Result	Execution time	Memory
845084		vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	125 ms	21488 KiB

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 / 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