oj.uz

Submission #845202

# Submission time Handle Problem Language Result Execution time Memory
845202 2023-09-06T12:34:16 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 58 ms 11864 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005

const int modulo = 1e9 + 7;

int dist[N], ans[N], done[N];
vector<int> adj[N];


int32_t main()
{
	fastio();


	int n, m, q, k;
	cin>>n>>m>>q>>k;

	int cnt = n;
	for (int i = 1; i <= q; i++){
		int node;
		cin>>node;
		done[node] = 1;
		cnt--;
	}

	for (int i = 1; i <= m; i++){
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}


	int step = 1;
	while(cnt > 0){
		queue<int> qu;
		for (int i = 1; i <= n; i++){
			if (done[i]) dist[i] = 0, qu.push(i);
		}

		while(!qu.empty()){
			int top = qu.front();
			qu.pop();
			if (dist[top] >= k * step) break;
			for (auto i : adj[top]){
				if (done[i]) continue;
				done[i] = 1;
				qu.push(i);
				dist[i] = dist[top] + 1;
				ans[i] = step;
				cnt--;
			}
		}
		step++;
	}

	for (int i = 1; i <= n; i++){
		cout<<ans[i]<<sp;
	}
	cout<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11344 KB Output is correct
2 Correct 49 ms 11712 KB Output is correct
3 Correct 52 ms 11712 KB Output is correct
4 Correct 40 ms 11088 KB Output is correct
5 Correct 41 ms 11096 KB Output is correct
6 Correct 50 ms 11808 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11600 KB Output is correct
2 Correct 58 ms 11860 KB Output is correct
3 Correct 49 ms 11684 KB Output is correct
4 Correct 49 ms 11588 KB Output is correct
5 Correct 47 ms 11608 KB Output is correct
6 Correct 42 ms 11344 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11600 KB Output is correct
2 Correct 49 ms 11856 KB Output is correct
3 Correct 53 ms 11776 KB Output is correct
4 Correct 48 ms 11608 KB Output is correct
5 Correct 45 ms 11344 KB Output is correct
6 Correct 46 ms 11348 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11540 KB Output is correct
2 Correct 47 ms 11864 KB Output is correct
3 Correct 57 ms 11704 KB Output is correct
4 Correct 44 ms 11344 KB Output is correct
5 Correct 42 ms 11088 KB Output is correct
6 Correct 45 ms 11252 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11088 KB Output is correct
2 Correct 48 ms 11540 KB Output is correct
3 Correct 56 ms 11752 KB Output is correct
4 Correct 45 ms 11432 KB Output is correct
5 Correct 53 ms 11344 KB Output is correct
6 Correct 44 ms 11092 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11088 KB Output is correct
2 Correct 54 ms 11680 KB Output is correct
3 Correct 57 ms 11392 KB Output is correct
4 Correct 49 ms 11716 KB Output is correct
5 Correct 54 ms 11284 KB Output is correct
6 Correct 47 ms 11184 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11348 KB Output is correct
2 Correct 50 ms 11348 KB Output is correct
3 Correct 53 ms 11740 KB Output is correct
4 Correct 48 ms 11344 KB Output is correct
5 Correct 52 ms 11440 KB Output is correct
6 Correct 50 ms 11532 KB Output is correct