oj.uz

답안 #570054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570054 2022-05-28T13:48:09 Z angelo_torres Birmingham (COCI20_birmingham) C++17
70 / 70
 219 ms 14712 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 = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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