Submission #709954

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
709954	2023-03-15T01:24:06 Z	willychan	Birmingham (COCI20_birmingham)	C++14	70 / 70	127 ms	9184 KB

birmingham

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int N = 100000+5;
int dis[N];
vector<int> side[N];
int n,m,q,k;
int get(int g){
	g--;
	if(g==0) return 0;
	ll l = 0;ll r = 100005;
	while(r-l>1){
		ll mid=(l+r)/2;
		if(k*((mid*mid+mid)/2)>=g) r = mid;
		else l = mid;
	}
	return r;
}


int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q>>k;
	queue<int> bfs;
	for(int i=0;i<q;i++){
		int a;cin>>a;
		dis[a]=1;
		bfs.push(a);
	}
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		side[a].push_back(b);
		side[b].push_back(a);
	}
	while(bfs.size()){
		int cur = bfs.front();
		bfs.pop();
		for(auto i : side[cur]){
			if(!dis[i]){
				dis[i] = dis[cur]+1;
				bfs.push(i);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<get(dis[i])<<" ";
	}
	cout<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2680 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2672 KB	Output is correct
2	Correct	2 ms	2672 KB	Output is correct
3	Correct	2 ms	2676 KB	Output is correct
4	Correct	2 ms	2676 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	8812 KB	Output is correct
2	Correct	119 ms	8920 KB	Output is correct
3	Correct	95 ms	9004 KB	Output is correct
4	Correct	73 ms	8560 KB	Output is correct
5	Correct	73 ms	8568 KB	Output is correct
6	Correct	81 ms	9012 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	9036 KB	Output is correct
2	Correct	82 ms	8860 KB	Output is correct
3	Correct	88 ms	9028 KB	Output is correct
4	Correct	108 ms	9184 KB	Output is correct
5	Correct	81 ms	8888 KB	Output is correct
6	Correct	81 ms	8612 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	8780 KB	Output is correct
2	Correct	103 ms	9068 KB	Output is correct
3	Correct	81 ms	9048 KB	Output is correct
4	Correct	90 ms	8980 KB	Output is correct
5	Correct	74 ms	8756 KB	Output is correct
6	Correct	71 ms	8708 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	8564 KB	Output is correct
2	Correct	97 ms	8796 KB	Output is correct
3	Correct	92 ms	8892 KB	Output is correct
4	Correct	78 ms	8736 KB	Output is correct
5	Correct	81 ms	8492 KB	Output is correct
6	Correct	73 ms	8648 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	8556 KB	Output is correct
2	Correct	74 ms	8804 KB	Output is correct
3	Correct	109 ms	8688 KB	Output is correct
4	Correct	93 ms	8772 KB	Output is correct
5	Correct	89 ms	8688 KB	Output is correct
6	Correct	60 ms	8524 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	8632 KB	Output is correct
2	Correct	100 ms	9044 KB	Output is correct
3	Correct	70 ms	8556 KB	Output is correct
4	Correct	80 ms	8912 KB	Output is correct
5	Correct	71 ms	8564 KB	Output is correct
6	Correct	76 ms	8684 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	8672 KB	Output is correct
2	Correct	85 ms	8524 KB	Output is correct
3	Correct	86 ms	9036 KB	Output is correct
4	Correct	89 ms	8576 KB	Output is correct
5	Correct	99 ms	8872 KB	Output is correct
6	Correct	76 ms	9028 KB	Output is correct

Submission #709954

Compilation message