oj.uz

Submission #604357

# Submission time Handle Problem Language Result Execution time Memory
604357 2022-07-25T04:37:17 Z Plurm Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 70168 KB 
#include <bits/stdc++.h>
using namespace std;

vector<short> g[100005];
short dist[5005][5005];
short fastqueue[8 * 1048576];
int hidx = 0;
int tidx = 0;
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) {
        g[i].push_back((short)j);
      }
    }
  }
  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:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~
events.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51668 KB Output is correct
2 Execution timed out 1578 ms 52724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51636 KB Output is correct
2 Correct 24 ms 51668 KB Output is correct
3 Correct 30 ms 52552 KB Output is correct
4 Correct 27 ms 52092 KB Output is correct
5 Correct 32 ms 52628 KB Output is correct
6 Correct 62 ms 52612 KB Output is correct
7 Correct 184 ms 53476 KB Output is correct
8 Correct 186 ms 53968 KB Output is correct
9 Correct 943 ms 55676 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51636 KB Output is correct
2 Correct 24 ms 51668 KB Output is correct
3 Correct 30 ms 52552 KB Output is correct
4 Correct 27 ms 52092 KB Output is correct
5 Correct 32 ms 52628 KB Output is correct
6 Correct 62 ms 52612 KB Output is correct
7 Correct 184 ms 53476 KB Output is correct
8 Correct 186 ms 53968 KB Output is correct
9 Correct 943 ms 55676 KB Output is correct
10 Correct 24 ms 51668 KB Output is correct
11 Correct 22 ms 51588 KB Output is correct
12 Correct 37 ms 52672 KB Output is correct
13 Correct 29 ms 52176 KB Output is correct
14 Correct 32 ms 52620 KB Output is correct
15 Correct 62 ms 52628 KB Output is correct
16 Correct 153 ms 53460 KB Output is correct
17 Correct 183 ms 53972 KB Output is correct
18 Correct 935 ms 55604 KB Output is correct
19 Execution timed out 1583 ms 70168 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51636 KB Output is correct
2 Correct 24 ms 51668 KB Output is correct
3 Correct 30 ms 52552 KB Output is correct
4 Correct 27 ms 52092 KB Output is correct
5 Correct 32 ms 52628 KB Output is correct
6 Correct 62 ms 52612 KB Output is correct
7 Correct 184 ms 53476 KB Output is correct
8 Correct 186 ms 53968 KB Output is correct
9 Correct 943 ms 55676 KB Output is correct
10 Correct 20 ms 51616 KB Output is correct
11 Correct 21 ms 51668 KB Output is correct
12 Correct 33 ms 52664 KB Output is correct
13 Correct 29 ms 52180 KB Output is correct
14 Correct 34 ms 52664 KB Output is correct
15 Correct 78 ms 52668 KB Output is correct
16 Correct 159 ms 53356 KB Output is correct
17 Correct 180 ms 53896 KB Output is correct
18 Correct 918 ms 55628 KB Output is correct
19 Execution timed out 1585 ms 52812 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 1584 ms 52756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51668 KB Output is correct
2 Execution timed out 1578 ms 52724 KB Time limit exceeded
3 Halted 0 ms 0 KB -