Submission #570054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
570054	2022-05-28T13:48:09 Z	angelo_torres	Birmingham (COCI20_birmingham)	C++17	70 / 70	219 ms	14712 KB

birmingham

#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define sz(s) (ll) (s.size())

using namespace std;
typedef long long ll;
typedef vector<ll> vll;

const int N = 1e5 + 20;
const ll mod = 1e9 + 7;

ll n,m,q,k,dis[N],vis[N];
vll ih,adj[N];


void multi_bfs(){
	f(i,1,n+1) dis[i] = (n<<1), vis[i] = 0;
	queue<ll> qe;
	for(auto it : ih){
		dis[it] = 0;
		qe.push(it);
	}
	while(!qe.empty()){
		ll v = qe.front();
		qe.pop();
		if(vis[v]) continue;
		vis[v] = 1;
		for(auto u : adj[v]){
			dis[u] = min(dis[u],dis[v]+1);
			if(vis[u]) continue;
			qe.push(u);
		}
	}
}

int main(){
	cin >> n >> m >> q >> k;
	ih.resize(q);
	f(i,0,q) cin >> ih[i];
	f(i,0,m){
		ll u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	multi_bfs();
	f(i,1,n+1){
		if(dis[i] == 0){
			cout << 0 << " ";
			continue;
		}
		ll gr = (dis[i]+k-1)/k;	
		ll tr = (ll) sqrt(8*gr+1);
		if(tr*tr != 8*gr+1) tr++;
		cout << (tr>>1) << " ";
	}
	cout << endl;
	return 0;
}

Subtask #1
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 #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2616 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	3 ms	2544 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 #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	3 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	1 ms	2644 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	193 ms	12476 KB	Output is correct
2	Correct	171 ms	13532 KB	Output is correct
3	Correct	178 ms	14708 KB	Output is correct
4	Correct	160 ms	11848 KB	Output is correct
5	Correct	135 ms	12132 KB	Output is correct
6	Correct	178 ms	14712 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	13180 KB	Output is correct
2	Correct	161 ms	13136 KB	Output is correct
3	Correct	198 ms	13804 KB	Output is correct
4	Correct	188 ms	13608 KB	Output is correct
5	Correct	154 ms	13176 KB	Output is correct
6	Correct	164 ms	13536 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	12640 KB	Output is correct
2	Correct	165 ms	13580 KB	Output is correct
3	Correct	176 ms	14540 KB	Output is correct
4	Correct	193 ms	13560 KB	Output is correct
5	Correct	155 ms	12544 KB	Output is correct
6	Correct	182 ms	13596 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	11852 KB	Output is correct
2	Correct	152 ms	13120 KB	Output is correct
3	Correct	171 ms	13884 KB	Output is correct
4	Correct	196 ms	12600 KB	Output is correct
5	Correct	141 ms	12100 KB	Output is correct
6	Correct	150 ms	13360 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	11928 KB	Output is correct
2	Correct	163 ms	12836 KB	Output is correct
3	Correct	155 ms	13060 KB	Output is correct
4	Correct	174 ms	12500 KB	Output is correct
5	Correct	143 ms	12696 KB	Output is correct
6	Correct	159 ms	13260 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	172 ms	12164 KB	Output is correct
2	Correct	150 ms	12824 KB	Output is correct
3	Correct	162 ms	13168 KB	Output is correct
4	Correct	188 ms	13088 KB	Output is correct
5	Correct	147 ms	12440 KB	Output is correct
6	Correct	166 ms	13696 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	162 ms	12272 KB	Output is correct
2	Correct	162 ms	11920 KB	Output is correct
3	Correct	198 ms	14284 KB	Output is correct
4	Correct	167 ms	12520 KB	Output is correct
5	Correct	154 ms	12872 KB	Output is correct
6	Correct	191 ms	14704 KB	Output is correct

Submission #570054

Compilation message