Submission #373070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373070	2021-03-03T08:47:21 Z	Nimbostratus	Birmingham (COCI20_birmingham)	C++17	70 / 70	140 ms	13164 KB

birmingham

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define ppb pop_back
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define cln(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int int
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9;
const int mod = 1e9+7;

vector<int> adj[maxn];
int n,m,qq,k,dist[maxn],src[maxn];
bool vis[maxn];


void bfs() {
	queue<int> q;
	for(int i=1;i<=qq;i++) {
		q.push(src[i]);
		vis[src[i]] = true;
	}
	while(not q.empty()) {
		int u = q.front();
		q.pop();
		for(int v : adj[u]) {
			if(vis[v]) continue;
			vis[v] = true;
			dist[v] = dist[u]+1; 
			q.push(v);
		}
	}
}

int root(int x) {
	ll l = 0 , r = x , mid;
	while(l < r-1) {
		mid = (l+r)/2;
		if(mid*(mid+1)/2*k == x) return mid;
		else if(mid*(mid+1)/2*k < x) l = mid+1;
		else r = mid;
	}
	if(l*(l+1)/2*k >= x) return l;
	return r;
}

int32_t main () {
	//freopen("in","r",stdin); freopen("out","w",stdout);
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> m >> qq >> k;
	for(int i=1;i<=qq;i++) cin >> src[i];
	while(m--) {
		int x,y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	bfs();
	for(int i=1;i<=n;i++) cout << root(dist[i]) << " ";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	12012 KB	Output is correct
2	Correct	112 ms	12396 KB	Output is correct
3	Correct	119 ms	12900 KB	Output is correct
4	Correct	90 ms	11372 KB	Output is correct
5	Correct	92 ms	11628 KB	Output is correct
6	Correct	107 ms	13164 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	12396 KB	Output is correct
2	Correct	111 ms	12352 KB	Output is correct
3	Correct	111 ms	12652 KB	Output is correct
4	Correct	109 ms	12524 KB	Output is correct
5	Correct	120 ms	12268 KB	Output is correct
6	Correct	101 ms	12396 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	12012 KB	Output is correct
2	Correct	116 ms	12524 KB	Output is correct
3	Correct	140 ms	12780 KB	Output is correct
4	Correct	127 ms	12524 KB	Output is correct
5	Correct	96 ms	11756 KB	Output is correct
6	Correct	115 ms	12524 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	11692 KB	Output is correct
2	Correct	114 ms	12268 KB	Output is correct
3	Correct	109 ms	12780 KB	Output is correct
4	Correct	112 ms	11884 KB	Output is correct
5	Correct	88 ms	11500 KB	Output is correct
6	Correct	89 ms	12140 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	11628 KB	Output is correct
2	Correct	107 ms	12012 KB	Output is correct
3	Correct	106 ms	12280 KB	Output is correct
4	Correct	105 ms	11756 KB	Output is correct
5	Correct	100 ms	12012 KB	Output is correct
6	Correct	90 ms	12124 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	11804 KB	Output is correct
2	Correct	106 ms	12140 KB	Output is correct
3	Correct	94 ms	12140 KB	Output is correct
4	Correct	106 ms	12396 KB	Output is correct
5	Correct	103 ms	11756 KB	Output is correct
6	Correct	92 ms	12268 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	11756 KB	Output is correct
2	Correct	100 ms	11500 KB	Output is correct
3	Correct	132 ms	12780 KB	Output is correct
4	Correct	94 ms	11904 KB	Output is correct
5	Correct	102 ms	12152 KB	Output is correct
6	Correct	134 ms	13036 KB	Output is correct

Submission #373070

Compilation message