oj.uz

답안 #845084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845084 2023-09-06T11:53:23 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 125 ms 21488 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n,m,q,k,vis[N],ans[N];
vector < int > graph[N];
queue < pair < int , int > > bfs;
void solve(){
	cin >> n >> m >> q >> k;
	memset(vis , 0 , sizeof(vis));
	for(int i = 0;i<q;i++){
		int u;cin >> u;
		bfs.push({u,0});
	}
	for(int i = 0;i<m;i++){
		int u,v;cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	map < int , int > bruh;
	bruh[0] = 0;
	int last = 0;
	for(int i = 1;i<=n;i++){
		for(int j = last+1;j <= (last + i * k);j++)bruh[j] = i;
		last += i * k;
		if(last > n)break;
	}
	while(bfs.size()){
		int node = bfs.front().first , dist = bfs.front().second;
		bfs.pop();
		if(vis[node])continue;
		vis[node] = 1;
		ans[node] = bruh[dist];
		for(auto itr : graph[node]){
			bfs.push({itr,dist+1});
		}
	}
	for(int i = 1;i<=n;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3216 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3160 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 13448 KB Output is correct
2 Correct 83 ms 13696 KB Output is correct
3 Correct 100 ms 14500 KB Output is correct
4 Correct 75 ms 13036 KB Output is correct
5 Correct 107 ms 19112 KB Output is correct
6 Correct 97 ms 14964 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 13780 KB Output is correct
2 Correct 72 ms 13860 KB Output is correct
3 Correct 75 ms 14072 KB Output is correct
4 Correct 106 ms 13904 KB Output is correct
5 Correct 104 ms 16464 KB Output is correct
6 Correct 99 ms 14104 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 13580 KB Output is correct
2 Correct 105 ms 13788 KB Output is correct
3 Correct 73 ms 14416 KB Output is correct
4 Correct 110 ms 13920 KB Output is correct
5 Correct 93 ms 16152 KB Output is correct
6 Correct 65 ms 13908 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 13136 KB Output is correct
2 Correct 68 ms 13816 KB Output is correct
3 Correct 116 ms 14492 KB Output is correct
4 Correct 65 ms 13396 KB Output is correct
5 Correct 89 ms 17724 KB Output is correct
6 Correct 85 ms 13904 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 13196 KB Output is correct
2 Correct 91 ms 13424 KB Output is correct
3 Correct 78 ms 13668 KB Output is correct
4 Correct 71 ms 13220 KB Output is correct
5 Correct 95 ms 21488 KB Output is correct
6 Correct 89 ms 13656 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 13192 KB Output is correct
2 Correct 65 ms 13392 KB Output is correct
3 Correct 125 ms 13652 KB Output is correct
4 Correct 98 ms 13652 KB Output is correct
5 Correct 114 ms 18232 KB Output is correct
6 Correct 80 ms 14140 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 13336 KB Output is correct
2 Correct 67 ms 13020 KB Output is correct
3 Correct 86 ms 14400 KB Output is correct
4 Correct 77 ms 13396 KB Output is correct
5 Correct 82 ms 17288 KB Output is correct
6 Correct 75 ms 14676 KB Output is correct