Submission #878372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878372	2023-11-24T08:58:49 Z	vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	58 ms	10964 KB

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.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	604 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	500 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	9736 KB	Output is correct
2	Correct	58 ms	10068 KB	Output is correct
3	Correct	58 ms	10492 KB	Output is correct
4	Correct	43 ms	9128 KB	Output is correct
5	Correct	46 ms	9300 KB	Output is correct
6	Correct	58 ms	10964 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	10064 KB	Output is correct
2	Correct	51 ms	9928 KB	Output is correct
3	Correct	52 ms	10220 KB	Output is correct
4	Correct	53 ms	10064 KB	Output is correct
5	Correct	49 ms	9812 KB	Output is correct
6	Correct	46 ms	10200 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	9596 KB	Output is correct
2	Correct	50 ms	10164 KB	Output is correct
3	Correct	53 ms	10456 KB	Output is correct
4	Correct	52 ms	10116 KB	Output is correct
5	Correct	46 ms	9532 KB	Output is correct
6	Correct	48 ms	10448 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	9300 KB	Output is correct
2	Correct	49 ms	9812 KB	Output is correct
3	Correct	52 ms	10412 KB	Output is correct
4	Correct	48 ms	9556 KB	Output is correct
5	Correct	53 ms	9428 KB	Output is correct
6	Correct	48 ms	10052 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	9300 KB	Output is correct
2	Correct	53 ms	9728 KB	Output is correct
3	Correct	47 ms	9812 KB	Output is correct
4	Correct	46 ms	9560 KB	Output is correct
5	Correct	45 ms	9736 KB	Output is correct
6	Correct	48 ms	9940 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	9336 KB	Output is correct
2	Correct	47 ms	10020 KB	Output is correct
3	Correct	48 ms	9908 KB	Output is correct
4	Correct	55 ms	9808 KB	Output is correct
5	Correct	45 ms	9544 KB	Output is correct
6	Correct	52 ms	10204 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	9556 KB	Output is correct
2	Correct	43 ms	9256 KB	Output is correct
3	Correct	52 ms	10520 KB	Output is correct
4	Correct	46 ms	9552 KB	Output is correct
5	Correct	47 ms	9624 KB	Output is correct
6	Correct	55 ms	10708 KB	Output is correct

Submission #878372

Compilation message