oj.uz

Submission #998982

# Submission time Handle Problem Language Result Execution time Memory
998982 2024-06-15T03:11:08 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 102 ms 10288 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
int n, m, q, k;
vector<int> G[N];
int dist[N];

void bfs()
{
  queue<int> Q;
  for(int i = 1; i <= n; i ++)
    if(dist[i] == 0) Q.push(i);

  while(Q.size())
    {
      int u = Q.front();
      Q.pop();
      for(int v : G[u])
	if(dist[u] + 1 < dist[v])
	  {
	    dist[v] = dist[u] + 1;
	    Q.push(v);
	  }
    }
}

int main()
{
  cin >> n >> m >> q >> k;

  for(int i = 1; i <= n; i ++)
    dist[i] = N * 4;
  
  for(int i = 0; i < q; i ++)
    {
      int x;
      cin >> x;
      dist[x] = 0;
    }

  for(int i = 0; i < m; i ++)
    {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }

  bfs();

  for(int i = 1; i <= n; i ++)
    {
      int x = 0, add = 0, sm = 0;
      while(dist[i] > add)
	{
	  x ++;
	  sm += k;
	  add += sm;
	}
      cout << x << ' ';
      
    }
  cout << endl;
  return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 7484 KB Output is correct
2 Correct 90 ms 9972 KB Output is correct
3 Correct 102 ms 10276 KB Output is correct
4 Correct 71 ms 8788 KB Output is correct
5 Correct 75 ms 9044 KB Output is correct
6 Correct 92 ms 10288 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7760 KB Output is correct
2 Correct 88 ms 9556 KB Output is correct
3 Correct 88 ms 10008 KB Output is correct
4 Correct 94 ms 10064 KB Output is correct
5 Correct 85 ms 9812 KB Output is correct
6 Correct 85 ms 9552 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7508 KB Output is correct
2 Correct 88 ms 9860 KB Output is correct
3 Correct 92 ms 10068 KB Output is correct
4 Correct 90 ms 9808 KB Output is correct
5 Correct 79 ms 9248 KB Output is correct
6 Correct 85 ms 9552 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7248 KB Output is correct
2 Correct 85 ms 9552 KB Output is correct
3 Correct 88 ms 9948 KB Output is correct
4 Correct 82 ms 9296 KB Output is correct
5 Correct 73 ms 9044 KB Output is correct
6 Correct 91 ms 9396 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7256 KB Output is correct
2 Correct 80 ms 7448 KB Output is correct
3 Correct 85 ms 9296 KB Output is correct
4 Correct 77 ms 9276 KB Output is correct
5 Correct 82 ms 9300 KB Output is correct
6 Correct 80 ms 9296 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7156 KB Output is correct
2 Correct 80 ms 9552 KB Output is correct
3 Correct 83 ms 9388 KB Output is correct
4 Correct 89 ms 9560 KB Output is correct
5 Correct 82 ms 9280 KB Output is correct
6 Correct 87 ms 9392 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7252 KB Output is correct
2 Correct 70 ms 9040 KB Output is correct
3 Correct 90 ms 10064 KB Output is correct
4 Correct 79 ms 9176 KB Output is correct
5 Correct 82 ms 9556 KB Output is correct
6 Correct 97 ms 10068 KB Output is correct