Submission #845414

#	Time	Username	Problem	Language	Result	Execution time	Memory
845414		vjudge1	Birmingham (COCI20_birmingham)	C++17	70 / 70	207 ms	10440 KiB

birmingham

// clang-format off
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define ll long long
#define lg2(x) (63 - __builtin_clzll(x))
#define db cerr << "BREAK\n"
#define fp(...) fprintf(stderr, __VA_ARGS__)
#define rs(a) a.resize(n)
#define hizli cin.tie(0);ios_base::sync_with_stdio(0)
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(a, b) for (int a = 0; a < b; a++)
#define af(x) for(auto&a:x)fp("%d ",a);fp("\n")
#define ff first
#define ss second
#define job main
// clang-format on
template <typename... Args> void in(Args &&...args) {
  (std::cin >> ... >> args);
}
const int N = 2e5 + 5, MOD = 1e9 + 7;
/*
~Y .5. J~ ~J .5. 5: 77 :5  5: ?! ^Y ~J .5. Y^ ~? .5..Y^ !? .
^J .5. ?! ^J .5. Y: !7 :P^^G~.J7 ^Y ~J .5. Y^ ~J .5..Y^ 7? .
^Y .5. ?! ~J .5. Y^.Y##&&&@@&&&&G55 ^J .5. J~ ~? .5. Y~ !J .
^Y .5. J! ~J .5. 5#&@@@&&&@&@@@@@@&J!J .5. J~ ~J .5. Y^ !J .
:Y  5: ?! :Y .5^5&@@@@&&&&&&&@@@@&@@&5 .5. J~ ~J .5. Y~ ~Y .
:5  5: ?! ^Y  P&@&&&&&&&&&&&&&&&&&&&&&!.P. Y~ ^J .5. Y~ ~J..
.5. Y: 77 ^Y .B&&&&&&&&&&&&&&B5YYG&&&@&:5. J! ~Y .5. J~ ~J .
.5. Y^ 77 ^Y ?&&&&&&&&&&&B5J7!7??JP&&@@YY. ?! ~Y .5. Y~ ~Y .
.5  Y^ !7 ^Y J#BP5555B#G7~~~!!7?JY5B@@@P5: J! ~J .P. J~ ~J..
.5  5: 7? ^Y ~&#5J?7!7?!!77!!!!7?J5P#@@BG! Y! !Y .P. J~ ~J .
.5  Y^ !J :5 .G&PYJ77!!~~!!~~!!?JY5PG&&P5~ Y7 ~Y .P. J~ ~Y .
.5. Y^ !J :5  Y&#5J7777!!777JPGBBBGGPB&PY^ J7 ^5 .P: J~ ~Y..
.P. Y~ !Y .5  YG&GP55PGP5J?5#BPGGG5Y5G#55: ?7 :5..P: ?! ^5..
.5. J~ !Y :5. 5^5#GB#BBGP5!?5YJJ?7?J5GG55: ?? :P..P: ?7 ^P..
.P. J~ !Y :5. 5:.PPJYYYJ?Y!~?J?77!7J5GB#B: ?? :P..P: ?7 ^5.
.P. J! ~Y .P. 5^ !5Y?777?57^7JYJ??J5PBB&@G.7? :P..P: ?? :5..
.P. ?7 ^Y .P. 5^ 77^PJ??7Y5?YG5JJ5PPGB##&@&BJ :P..P: ?? :5.
 P: ?7 ^5 .P. Y^ 7J 7GYJ?JPGGP5PGGPGB#BB&@@@&J~P. 5^ 7J :P.
 5: ?7 :5 .P. Y~ 7PJB&BPPGGPP5PGGY5G##G&@@@&@@&&Y:5^ 7J :P.
 5: ?? :5 .P^:PGG&@@@@@&BG55PPPYJY5#&B#&&&&&&&&&@&&J.!? :P.
 5^ !J:!BYP#&&&&&@@@@@@@@&B5YYYYPG#&B#&&&&&&&@@&&&&&#B5..P.
 5~ Y&&&&&&&&&&&&&@@&@@@@@@####&&&&##&&&&&&&&@&&&&&&&&&#GB:
 Y!J&&&&&&&&&&&&&&&&&&@@@@@&##&&&&##&&&&&&&&&&&&&&&&&&&&&&#J
 ?J#&&&&&&&&&&&&&&&&&&&&@@@###&&&BB&&&&&&&&&&&&&&&&&&&&&&&&&
 ?B&&&&&&&&&&&&&&&&&&&&&&@@&BBBBGB&&&&&&&&&@@&&&&&&&&&&&&&&&
 ?&&&&&&&&&&&&&&&&&&&&&&&@@@&BGGB&&&&&&&&&@&&&&&&&&&&&&&&&&&
 J&&&&&&&&&&&&&&&&&&&&&&@@@@@@@@&&&&&&&&&&&&&&&&&&&&&&&&&&@@
 Y&&&&&&&&&&&&&&&&&&&&&&@@@@@@@@&&&&&&&&&&&&&&&&&&&&&&&&@&@@*/
vector<vector<int>> adj;

struct ben{
  int first,second;
  bool operator<(const ben &other){
    return first > other.first;
  }
  bool comp(ben &other){
    return first > other.first;
  }
};

int job() {
  hizli;
  int n, m, q, k;
  in(n, m, q, k);
  adj.resize(n);
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
  vector<int> vdepth(n), mark(n);
  for (int i = 0; i < q; i++) {
    int vip;
    in(vip);
    pq.push({0, vip-1});
    mark[vip-1]=1;
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  while (!pq.empty()) {
    int depth = pq.top().ff, node = pq.top().ss;
    pq.pop();
    for (auto &a : adj[node]) {
      if (!mark[a]) {
        pq.push({depth + 1, a});
        // cerr << node+1 << "dan" << a+1 << "ya";
        vdepth[a]=depth+1;
        mark[a] = 1;
      }
    }
  }
  vector<unsigned ll> ar;
  for(int i=1;i<2000;i++){
    ar.pb(k*i*(i+1)/2);
  }
  // for(auto&a:ar){cout << a << endl;}
  for(int i=0;i<n;i++){
    auto it = lower_bound(all(ar),ceil(vdepth[i]));
    int ans = it-ar.begin()+1;
    // if(*it == ceil(vdepth[i]))
      // ans--;
    if(vdepth[i]==0){
      ans=0;
    }
    cout << ans << endl;
    // cout << ceil(vdepth[i]) << " " << *it << endl;
  }
}

• 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