Submission #845128

#	Time	Username	Problem	Language	Result	Execution time	Memory
845128		vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	77 ms	9892 KiB

birmingham

// 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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5