oj.uz

답안 #878372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878372 2023-11-24T08:58:49 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 58 ms 10964 KB 
//~ #pragma GCC optimize("O3,unroll-loops")
//~ #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h> 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define endl "\n"
//~ #define int long long

using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef long long ll;
//~ const int mod =998244353;
const int mod =1e9+7;

int n, m, q, k;
vector<vector<int>> graph;
vector<int> dist;
vector<bool> vis;
vector<int> inp;
int sum[100005];
void bfs(){
	queue<ii> q;
	for(auto it: inp){
		q.push({it, 0});
		vis[it]=true;
	}
	while(!q.empty()){
		int node=q.front().fi, d=q.front().se;
		q.pop();
		dist[node]=d;
		for(auto it: graph[node]){
			if(vis[it])continue;
			q.push({it, d+1});
			vis[it]=true;
		}
	}
}



int32_t main(){	
	fast;	
	cin>>n>>m>>q>>k;
	graph.assign(n+5, vector<int>());
	vis.assign(n+5, false);
	dist.assign(n+5, 0);
	for(int i=1;i<=q;i++){
		int ind;
		cin>>ind;
		inp.pb(ind);
	}
	for(int i=1;i<=m;i++){
		int a, b;
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	bfs();
	int N=0;
	for(int i=1;sum[i-1]<n;i++){
		sum[i]=i*((i*k)+k)/2;
		N=i;
		//~ cout<<sum[i]<<" ";
	
	}
	for(int i=1;i<=n;i++){
		int ans= lower_bound(sum, sum+N+1, dist[i])-sum;
		cout<<ans<<" ";
	}
	cout<<endl;
}

//~ 6 8 2 2
//~ 6 4
//~ 1 3
//~ 1 5
//~ 1 6
//~ 2 5
//~ 2 6
//~ 3 4
//~ 3 5
//~ 5 6

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9736 KB Output is correct
2 Correct 58 ms 10068 KB Output is correct
3 Correct 58 ms 10492 KB Output is correct
4 Correct 43 ms 9128 KB Output is correct
5 Correct 46 ms 9300 KB Output is correct
6 Correct 58 ms 10964 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 10064 KB Output is correct
2 Correct 51 ms 9928 KB Output is correct
3 Correct 52 ms 10220 KB Output is correct
4 Correct 53 ms 10064 KB Output is correct
5 Correct 49 ms 9812 KB Output is correct
6 Correct 46 ms 10200 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 9596 KB Output is correct
2 Correct 50 ms 10164 KB Output is correct
3 Correct 53 ms 10456 KB Output is correct
4 Correct 52 ms 10116 KB Output is correct
5 Correct 46 ms 9532 KB Output is correct
6 Correct 48 ms 10448 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 9300 KB Output is correct
2 Correct 49 ms 9812 KB Output is correct
3 Correct 52 ms 10412 KB Output is correct
4 Correct 48 ms 9556 KB Output is correct
5 Correct 53 ms 9428 KB Output is correct
6 Correct 48 ms 10052 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 9300 KB Output is correct
2 Correct 53 ms 9728 KB Output is correct
3 Correct 47 ms 9812 KB Output is correct
4 Correct 46 ms 9560 KB Output is correct
5 Correct 45 ms 9736 KB Output is correct
6 Correct 48 ms 9940 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 9336 KB Output is correct
2 Correct 47 ms 10020 KB Output is correct
3 Correct 48 ms 9908 KB Output is correct
4 Correct 55 ms 9808 KB Output is correct
5 Correct 45 ms 9544 KB Output is correct
6 Correct 52 ms 10204 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 9556 KB Output is correct
2 Correct 43 ms 9256 KB Output is correct
3 Correct 52 ms 10520 KB Output is correct
4 Correct 46 ms 9552 KB Output is correct
5 Correct 47 ms 9624 KB Output is correct
6 Correct 55 ms 10708 KB Output is correct