Submission #237635

#	Time	Username	Problem	Language	Result	Execution time	Memory
237635		akat	Birmingham (COCI20_birmingham)	C++14	70 / 70	138 ms	10744 KiB

birmingham

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,s,k,i,j,a,b,dist[N],wave[N];
	vector<int>adj[N];
	cin>>n>>m>>s>>k;
	memset(dist,-1,sizeof(dist));
	queue<int>q;
	for(i = 0; i < s; i++)
	{
		cin>>a;
		q.push(a);
		dist[a] = 0;
	}
	for(i = 0; i < m; i++)
	{
		cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	while(q.size())
	{
		a = q.front();
		q.pop();
		for(int x:adj[a])
		{
			if(dist[x] == -1)
			{
				dist[x] = dist[a] + 1;
				q.push(x);
			}
		}
	}
	wave[0] = 0;
	int curr = 0, old = 0;
	for(i = 1; curr < n; i++)
	{
		old = curr;
		curr += k * i;
		for(j = old + 1; j <= min(n,curr); j++)
			wave[j] = i;
	}
	for(i=1;i<=n;i++)
		cout<<wave[dist[i]]<<" \n"[i==n];
}

• 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