Submission #570054

#	Time	Username	Problem	Language	Result	Execution time	Memory
570054		angelo_torres	Birmingham (COCI20_birmingham)	C++17	70 / 70	219 ms	14712 KiB

birmingham

#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define sz(s) (ll) (s.size())

using namespace std;
typedef long long ll;
typedef vector<ll> vll;

const int N = 1e5 + 20;
const ll mod = 1e9 + 7;

ll n,m,q,k,dis[N],vis[N];
vll ih,adj[N];


void multi_bfs(){
	f(i,1,n+1) dis[i] = (n<<1), vis[i] = 0;
	queue<ll> qe;
	for(auto it : ih){
		dis[it] = 0;
		qe.push(it);
	}
	while(!qe.empty()){
		ll v = qe.front();
		qe.pop();
		if(vis[v]) continue;
		vis[v] = 1;
		for(auto u : adj[v]){
			dis[u] = min(dis[u],dis[v]+1);
			if(vis[u]) continue;
			qe.push(u);
		}
	}
}

int main(){
	cin >> n >> m >> q >> k;
	ih.resize(q);
	f(i,0,q) cin >> ih[i];
	f(i,0,m){
		ll u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	multi_bfs();
	f(i,1,n+1){
		if(dis[i] == 0){
			cout << 0 << " ";
			continue;
		}
		ll gr = (dis[i]+k-1)/k;	
		ll tr = (ll) sqrt(8*gr+1);
		if(tr*tr != 8*gr+1) tr++;
		cout << (tr>>1) << " ";
	}
	cout << endl;
	return 0;
}

• 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