Submission #878372

#	Time	Username	Problem	Language	Result	Execution time	Memory
878372		vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	58 ms	10964 KiB

birmingham

//~ #pragma GCC optimize("O3,unroll-loops")
//~ #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h> 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define endl "\n"
//~ #define int long long

using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef long long ll;
//~ const int mod =998244353;
const int mod =1e9+7;

int n, m, q, k;
vector<vector<int>> graph;
vector<int> dist;
vector<bool> vis;
vector<int> inp;
int sum[100005];
void bfs(){
	queue<ii> q;
	for(auto it: inp){
		q.push({it, 0});
		vis[it]=true;
	}
	while(!q.empty()){
		int node=q.front().fi, d=q.front().se;
		q.pop();
		dist[node]=d;
		for(auto it: graph[node]){
			if(vis[it])continue;
			q.push({it, d+1});
			vis[it]=true;
		}
	}
}



int32_t main(){	
	fast;	
	cin>>n>>m>>q>>k;
	graph.assign(n+5, vector<int>());
	vis.assign(n+5, false);
	dist.assign(n+5, 0);
	for(int i=1;i<=q;i++){
		int ind;
		cin>>ind;
		inp.pb(ind);
	}
	for(int i=1;i<=m;i++){
		int a, b;
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	bfs();
	int N=0;
	for(int i=1;sum[i-1]<n;i++){
		sum[i]=i*((i*k)+k)/2;
		N=i;
		//~ cout<<sum[i]<<" ";
	
	}
	for(int i=1;i<=n;i++){
		int ans= lower_bound(sum, sum+N+1, dist[i])-sum;
		cout<<ans<<" ";
	}
	cout<<endl;
}

//~ 6 8 2 2
//~ 6 4
//~ 1 3
//~ 1 5
//~ 1 6
//~ 2 5
//~ 2 6
//~ 3 4
//~ 3 5
//~ 5 6

• 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