oj.uz

Submission #570052

# Submission time Handle Problem Language Result Execution time Memory
570052 2022-05-28T13:47:09 Z angelo_torres Birmingham (COCI20_birmingham) C++17
35 / 70
 6 ms 1284 KB 
#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 = 3e3 + 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 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1224 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1276 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -