oj.uz

Submission #246162

# Submission time Handle Problem Language Result Execution time Memory
246162 2020-07-08T10:16:42 Z alrad Birmingham (COCI20_birmingham) C++17
70 / 70
 132 ms 10616 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 2;

vector<vector<int> > g(N , vector<int>());

int main() {
   #ifdef judge
      ifstream cin("input.txt");
   #endif // judge
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n , m , que , k;
   cin >> n >> m >> que >> k;
   queue<int> q;
   vector<int> starts(que) , d(n + 1 , 0);
   vector<bool> used(n + 1 , false);
   for (int i = 0; i < que; i++) {
      cin >> starts[i];
      q.push(starts[i]);
      used[starts[i]] = true;
   }
   for (int i = 0; i < m; i++) {
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int to : g[v]) {
         if (!used[to]) {
            used[to] = true;
            q.push(to);
            d[to] = d[v] + 1;
         } else if (d[v] + 1 < d[to]) {
            q.push(to);
            d[to] = d[v] + 1;
         }
      }
   }
   auto getDay = [&](int dist) {
      int res = 0 , temp = 1;
      while (res < dist) {
         res += (temp * k);
         temp++;
      }
      return temp - 1;
   };
   for (int i = 1; i <= n; i++) {
      if (d[i] != 0) {
         cout << getDay(d[i]) << " ";
      } else {
         cout << 0 << " ";
      }
   }
   return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 8 ms 2688 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 8 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 9592 KB Output is correct
2 Correct 111 ms 9980 KB Output is correct
3 Correct 109 ms 10500 KB Output is correct
4 Correct 93 ms 9080 KB Output is correct
5 Correct 86 ms 9208 KB Output is correct
6 Correct 105 ms 10616 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9976 KB Output is correct
2 Correct 104 ms 9848 KB Output is correct
3 Correct 100 ms 10104 KB Output is correct
4 Correct 98 ms 10104 KB Output is correct
5 Correct 101 ms 9720 KB Output is correct
6 Correct 93 ms 9848 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9592 KB Output is correct
2 Correct 132 ms 10184 KB Output is correct
3 Correct 106 ms 10488 KB Output is correct
4 Correct 106 ms 9976 KB Output is correct
5 Correct 92 ms 9464 KB Output is correct
6 Correct 91 ms 9976 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 9080 KB Output is correct
2 Correct 98 ms 9720 KB Output is correct
3 Correct 100 ms 10312 KB Output is correct
4 Correct 103 ms 9596 KB Output is correct
5 Correct 98 ms 9080 KB Output is correct
6 Correct 106 ms 9852 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 9304 KB Output is correct
2 Correct 110 ms 9464 KB Output is correct
3 Correct 105 ms 9592 KB Output is correct
4 Correct 91 ms 9336 KB Output is correct
5 Correct 100 ms 9424 KB Output is correct
6 Correct 96 ms 9720 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9208 KB Output is correct
2 Correct 93 ms 9464 KB Output is correct
3 Correct 100 ms 9592 KB Output is correct
4 Correct 102 ms 9756 KB Output is correct
5 Correct 118 ms 9336 KB Output is correct
6 Correct 97 ms 10104 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 9336 KB Output is correct
2 Correct 82 ms 9080 KB Output is correct
3 Correct 120 ms 10360 KB Output is correct
4 Correct 98 ms 9336 KB Output is correct
5 Correct 95 ms 9592 KB Output is correct
6 Correct 101 ms 10616 KB Output is correct