oj.uz

Submission #612468

# Submission time Handle Problem Language Result Execution time Memory
612468 2022-07-29T15:34:14 Z Plurm Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 87396 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

vector<short> g[100005];
vector<short> rg[100005];
short dist[5005][5005];
short fastqueue[8 * 1048576];
int hidx = 0;
int tidx = 0;
int tmphsh[100005];
int main() {
  memset(dist, 0x3F, sizeof(dist));
  int n, q;
  scanf("%d%d", &n, &q);
  vector<pair<int, int>> events;
  for (int i = 1; i <= n; i++) {
    int s, e;
    scanf("%d%d", &s, &e);
    events.push_back({s, e});
  }
  for (int i = 0; i < n; i++) {
    vector<int> tmp;
    for (int j = 0; j < n; j++) {
      if (i == j)
        continue;
      if (events[j].first <= events[i].second &&
          events[i].second <= events[j].second) {
        rg[i].push_back((short)j);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int hsh = 0;
    for (short j : rg[i]) {
      hsh *= 53;
      hsh += j;
    }
    tmphsh[i] = hsh;
  }
  for (int i = 0; i < n; i++) {
    __gnu_pbds::cc_hash_table<int, short> mp;
    for (short j : rg[i]) {
      mp[tmphsh[j]] = j;
    }
    for (auto p : mp) {
      g[i].push_back(p.second);
    }
  }
  for (int i = 0; i < n; i++) {
    dist[i][i] = 0;
    fastqueue[tidx++] = i;
    while (hidx != tidx) {
      short u = fastqueue[hidx++];
      for (short v : g[u]) {
        if (dist[i][v] > dist[i][u] + 1) {
          dist[i][v] = dist[i][u] + 1;
          fastqueue[tidx++] = v;
        }
      }
    }
  }
  for (int i = 0; i < q; i++) {
    int s, e;
    scanf("%d%d", &s, &e);
    if (dist[s - 1][e - 1] > n)
      printf("impossible\n");
    else
      printf("%hd\n", dist[s - 1][e - 1]);
    // can e be reached by s?, if yes, what is the shortest path?
  }
  return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~
events.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53988 KB Output is correct
2 Execution timed out 1589 ms 55180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53972 KB Output is correct
2 Correct 22 ms 53992 KB Output is correct
3 Correct 31 ms 54996 KB Output is correct
4 Correct 31 ms 54584 KB Output is correct
5 Correct 33 ms 55104 KB Output is correct
6 Correct 93 ms 55468 KB Output is correct
7 Correct 215 ms 56648 KB Output is correct
8 Correct 313 ms 57684 KB Output is correct
9 Correct 1217 ms 60172 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53972 KB Output is correct
2 Correct 22 ms 53992 KB Output is correct
3 Correct 31 ms 54996 KB Output is correct
4 Correct 31 ms 54584 KB Output is correct
5 Correct 33 ms 55104 KB Output is correct
6 Correct 93 ms 55468 KB Output is correct
7 Correct 215 ms 56648 KB Output is correct
8 Correct 313 ms 57684 KB Output is correct
9 Correct 1217 ms 60172 KB Output is correct
10 Correct 26 ms 53964 KB Output is correct
11 Correct 21 ms 53972 KB Output is correct
12 Correct 34 ms 54988 KB Output is correct
13 Correct 30 ms 54476 KB Output is correct
14 Correct 36 ms 55092 KB Output is correct
15 Correct 89 ms 55480 KB Output is correct
16 Correct 217 ms 56564 KB Output is correct
17 Correct 262 ms 57676 KB Output is correct
18 Correct 1166 ms 60092 KB Output is correct
19 Execution timed out 1542 ms 87396 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53972 KB Output is correct
2 Correct 22 ms 53992 KB Output is correct
3 Correct 31 ms 54996 KB Output is correct
4 Correct 31 ms 54584 KB Output is correct
5 Correct 33 ms 55104 KB Output is correct
6 Correct 93 ms 55468 KB Output is correct
7 Correct 215 ms 56648 KB Output is correct
8 Correct 313 ms 57684 KB Output is correct
9 Correct 1217 ms 60172 KB Output is correct
10 Correct 21 ms 53972 KB Output is correct
11 Correct 22 ms 53984 KB Output is correct
12 Correct 32 ms 55080 KB Output is correct
13 Correct 29 ms 54556 KB Output is correct
14 Correct 39 ms 55016 KB Output is correct
15 Correct 90 ms 55396 KB Output is correct
16 Correct 224 ms 56684 KB Output is correct
17 Correct 266 ms 57708 KB Output is correct
18 Correct 1163 ms 59972 KB Output is correct
19 Execution timed out 1575 ms 56840 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 55136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53988 KB Output is correct
2 Execution timed out 1589 ms 55180 KB Time limit exceeded
3 Halted 0 ms 0 KB -