oj.uz

Submission #845128

# Submission time Handle Problem Language Result Execution time Memory
845128 2023-09-06T12:09:22 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 77 ms 9892 KB 
// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M, Q, K;
  cin >> N >> M >> Q >> K;
  vector<int> S(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> S[i];
    --S[i];
  }
  vector<vector<int>> g(N);
  for (int i = 0; i < M; ++i) {
    int X, Y;
    cin >> X >> Y;
    --X, --Y;
    g[X].push_back(Y);
    g[Y].push_back(X);
  }
  vector<int> dist(N, -1);
  for (auto x : S) {
    dist[x] = 0;
  }
  for (int it = 0; it < N; ++it) {
    int v = S[it];
    for (auto u : g[v]) {
      if (dist[u] == -1) {
        dist[u] = dist[v] + 1;
        S.push_back(u);
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    int low = 0, high = int(1e4);
    while (low < high) {
      int mid = (low + high) >> 1;
      if (mid * (mid + 1) / 2 >= (dist[i] + K - 1) / K) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    cout << low << ' ';
  }
}

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 600 KB Output is correct
3 Correct 0 ms 604 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 0 ms 460 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 56 ms 8132 KB Output is correct
2 Correct 68 ms 9316 KB Output is correct
3 Correct 65 ms 9872 KB Output is correct
4 Correct 59 ms 8908 KB Output is correct
5 Correct 60 ms 9316 KB Output is correct
6 Correct 77 ms 9308 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8140 KB Output is correct
2 Correct 67 ms 9232 KB Output is correct
3 Correct 73 ms 9172 KB Output is correct
4 Correct 61 ms 9420 KB Output is correct
5 Correct 57 ms 9720 KB Output is correct
6 Correct 50 ms 8816 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7960 KB Output is correct
2 Correct 58 ms 9424 KB Output is correct
3 Correct 63 ms 9892 KB Output is correct
4 Correct 66 ms 9456 KB Output is correct
5 Correct 50 ms 9144 KB Output is correct
6 Correct 55 ms 8744 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7636 KB Output is correct
2 Correct 63 ms 9420 KB Output is correct
3 Correct 63 ms 9432 KB Output is correct
4 Correct 64 ms 9172 KB Output is correct
5 Correct 52 ms 8892 KB Output is correct
6 Correct 54 ms 8616 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7708 KB Output is correct
2 Correct 54 ms 7944 KB Output is correct
3 Correct 58 ms 9052 KB Output is correct
4 Correct 62 ms 8916 KB Output is correct
5 Correct 59 ms 9156 KB Output is correct
6 Correct 59 ms 8616 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7616 KB Output is correct
2 Correct 62 ms 9068 KB Output is correct
3 Correct 62 ms 8868 KB Output is correct
4 Correct 67 ms 9168 KB Output is correct
5 Correct 52 ms 8904 KB Output is correct
6 Correct 60 ms 8784 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 7644 KB Output is correct
2 Correct 70 ms 8580 KB Output is correct
3 Correct 64 ms 9368 KB Output is correct
4 Correct 56 ms 9108 KB Output is correct
5 Correct 51 ms 9164 KB Output is correct
6 Correct 64 ms 9308 KB Output is correct