제출 #299192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299192		quanmcvn	Birmingham (COCI20_birmingham)	C++14	70 / 70	522 ms	18800 KiB

birmingham

#include <bits/stdc++.h>
#define fff "main"
#define For(i,a,b) for (auto i = a; i < b; ++i)
#define pb push_back
#define en cout << '\n';
using namespace std;

typedef signed long long int ll;
typedef std::vector<ll> vll;

vector<pair<ll,ll> > ct[100001];
ll d[100001];
ll know_first[100001];
ll n,m,q,k;

void spf(){
	priority_queue<pair<ll, ll >, vector<pair<ll,ll > >, greater<pair<ll, ll > > >pq;
	For (i,1,n+1) {
		d[i] = 99999999999;
		if (know_first[i]){
			d[i] = 0;
			pq.push({0,i});
		}
	}
	while (pq.size()) {
		ll u = pq.top().second;
		ll du = pq.top().first;
		pq.pop();
		if (du > d[u]) continue;
		for (auto f : ct[u]){
			ll v = f.second;
			ll w = f.first;
			if (d[v] > du + w) {
				d[v] = du + w;
				pq.push({d[v], v});
			}
		}
	}
}

ll sum_to(const ll &x){
	return (x * (x + 1)) / 2;
}

int main()
{
//	if (fopen(fff".inp","r")) {
//		freopen(fff".inp","r",stdin);
//		freopen(fff".out","w",stdout);
//	}
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q >> k;
	while (q--) {
		ll f;
		cin >> f;
		know_first[f] = 1;
	}
	while (m--){
		ll u, v; cin >> u >> v;
		ct[u].pb({1,v});
		ct[v].pb({1,u});
	}
	spf();
	vll check;
	for (ll i = 0; sum_to(i) <= n / k; ++i){
		check.pb(sum_to(i) * k);
	}
	For (i,1,n+1){
		cout << lower_bound(check.begin(),check.end(),d[i]) - check.begin() << ' ';
	}
    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