oj.uz

Submission #845414

# Submission time Handle Problem Language Result Execution time Memory
845414 2023-09-06T13:31:32 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 207 ms 10440 KB 
// 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.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9544 KB Output is correct
2 Correct 176 ms 9940 KB Output is correct
3 Correct 177 ms 10072 KB Output is correct
4 Correct 183 ms 9428 KB Output is correct
5 Correct 173 ms 9164 KB Output is correct
6 Correct 181 ms 10228 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 10440 KB Output is correct
2 Correct 181 ms 9948 KB Output is correct
3 Correct 172 ms 9804 KB Output is correct
4 Correct 174 ms 9936 KB Output is correct
5 Correct 207 ms 9820 KB Output is correct
6 Correct 168 ms 9716 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 9500 KB Output is correct
2 Correct 174 ms 9936 KB Output is correct
3 Correct 174 ms 10160 KB Output is correct
4 Correct 168 ms 9936 KB Output is correct
5 Correct 175 ms 9428 KB Output is correct
6 Correct 164 ms 9676 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 9340 KB Output is correct
2 Correct 171 ms 9876 KB Output is correct
3 Correct 172 ms 10076 KB Output is correct
4 Correct 198 ms 9704 KB Output is correct
5 Correct 164 ms 9280 KB Output is correct
6 Correct 163 ms 9676 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 9168 KB Output is correct
2 Correct 163 ms 9652 KB Output is correct
3 Correct 159 ms 9428 KB Output is correct
4 Correct 170 ms 9344 KB Output is correct
5 Correct 161 ms 9532 KB Output is correct
6 Correct 166 ms 9596 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9344 KB Output is correct
2 Correct 161 ms 9428 KB Output is correct
3 Correct 157 ms 9444 KB Output is correct
4 Correct 173 ms 9916 KB Output is correct
5 Correct 170 ms 9624 KB Output is correct
6 Correct 169 ms 9760 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 9304 KB Output is correct
2 Correct 186 ms 9456 KB Output is correct
3 Correct 178 ms 10048 KB Output is correct
4 Correct 170 ms 9360 KB Output is correct
5 Correct 173 ms 9668 KB Output is correct
6 Correct 191 ms 10288 KB Output is correct