oj.uz

Submission #845404

# Submission time Handle Problem Language Result Execution time Memory
845404 2023-09-06T13:29:30 Z vjudge1 Birmingham (COCI20_birmingham) C++17
45 / 70
 271 ms 8632 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() {
  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<ll> ar;
  for(int i=1;i<1000;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 344 KB Output is correct
2 Correct 1 ms 600 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 344 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 8224 KB Output is correct
2 Correct 225 ms 8468 KB Output is correct
3 Correct 254 ms 8448 KB Output is correct
4 Correct 208 ms 7956 KB Output is correct
5 Correct 234 ms 8428 KB Output is correct
6 Correct 238 ms 8284 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 8492 KB Output is correct
2 Correct 224 ms 8140 KB Output is correct
3 Correct 229 ms 8392 KB Output is correct
4 Correct 225 ms 8388 KB Output is correct
5 Incorrect 240 ms 8368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 8324 KB Output is correct
2 Correct 254 ms 8632 KB Output is correct
3 Correct 259 ms 8272 KB Output is correct
4 Correct 229 ms 8396 KB Output is correct
5 Incorrect 230 ms 8312 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8064 KB Output is correct
2 Correct 249 ms 8152 KB Output is correct
3 Correct 234 ms 8388 KB Output is correct
4 Correct 213 ms 8092 KB Output is correct
5 Incorrect 225 ms 8288 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 8016 KB Output is correct
2 Correct 225 ms 8368 KB Output is correct
3 Correct 232 ms 8032 KB Output is correct
4 Correct 226 ms 8024 KB Output is correct
5 Correct 218 ms 8176 KB Output is correct
6 Correct 271 ms 8156 KB Output is correct

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 8244 KB Output is correct
2 Correct 228 ms 8148 KB Output is correct
3 Correct 253 ms 7948 KB Output is correct
4 Correct 240 ms 8240 KB Output is correct
5 Incorrect 267 ms 8200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 8144 KB Output is correct
2 Correct 201 ms 7912 KB Output is correct
3 Correct 232 ms 8284 KB Output is correct
4 Correct 208 ms 8148 KB Output is correct
5 Incorrect 225 ms 8400 KB Output isn't correct
6 Halted 0 ms 0 KB -