oj.uz

Submission #845073

# Submission time Handle Problem Language Result Execution time Memory
845073 2023-09-06T11:50:47 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 81 ms 12884 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

void solve(){
  int n,m,q,k;
  cin >> n >> m >> q >> k;
  int dist[n+1];
  for(int i=1;i<=n;i++) dist[i]=100000000;
  queue<int> que;
  
  for(int i=1;i<=q;i++)
  {
  	int a; cin >> a;
  	dist[a]=0;
  	que.push(a);
  }

  vector<int> v[n+1];

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

  while(!que.empty())
  {
  	int c=que.front();
  	que.pop();
  	for(int x:v[c])
  	{
  	  if(dist[c] + 1 < dist[x])
  	  {
  	  	dist[x] = dist[c] + 1;
        que.push(x);
  	  }
  	}
  }

  for(int i=1;i<=n;i++)
  {
  	if(dist[i]==0)
  	{
  		cout << 0 << " ";
  		continue;
  	}
  	int ans=1;
  	int right=k;
  	while(dist[i]>right)
  	{
      ans++;
      right+=ans*k;
  	}
  	cout << ans << " ";
  }
  cout << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 456 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

# Verdict Execution time Memory 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
4 Correct 0 ms 348 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9748 KB Output is correct
2 Correct 79 ms 12628 KB Output is correct
3 Correct 71 ms 12884 KB Output is correct
4 Correct 64 ms 10832 KB Output is correct
5 Correct 56 ms 11172 KB Output is correct
6 Correct 73 ms 12876 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 10160 KB Output is correct
2 Correct 81 ms 12224 KB Output is correct
3 Correct 65 ms 12556 KB Output is correct
4 Correct 63 ms 12596 KB Output is correct
5 Correct 62 ms 12140 KB Output is correct
6 Correct 52 ms 11696 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9808 KB Output is correct
2 Correct 63 ms 12736 KB Output is correct
3 Correct 63 ms 12716 KB Output is correct
4 Correct 63 ms 12716 KB Output is correct
5 Correct 54 ms 11604 KB Output is correct
6 Correct 56 ms 11872 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9332 KB Output is correct
2 Correct 70 ms 12048 KB Output is correct
3 Correct 60 ms 12612 KB Output is correct
4 Correct 53 ms 11812 KB Output is correct
5 Correct 52 ms 11092 KB Output is correct
6 Correct 53 ms 11864 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9556 KB Output is correct
2 Correct 55 ms 11740 KB Output is correct
3 Correct 55 ms 11748 KB Output is correct
4 Correct 55 ms 11688 KB Output is correct
5 Correct 53 ms 11772 KB Output is correct
6 Correct 51 ms 11604 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9552 KB Output is correct
2 Correct 54 ms 11816 KB Output is correct
3 Correct 59 ms 11600 KB Output is correct
4 Correct 57 ms 12172 KB Output is correct
5 Correct 51 ms 11492 KB Output is correct
6 Correct 52 ms 11860 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9744 KB Output is correct
2 Correct 49 ms 11088 KB Output is correct
3 Correct 58 ms 12624 KB Output is correct
4 Correct 62 ms 11900 KB Output is correct
5 Correct 57 ms 11912 KB Output is correct
6 Correct 64 ms 12672 KB Output is correct