oj.uz

Submission #604351

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

vector<int> g[100005];
short dist[5005][5005];
int main() {
  memset(dist, 0x3F, sizeof(dist));
  int n, q;
  scanf("%d%d", &n, &q);
  vector<pair<int, int>> events;
  int k = sqrt(n);
  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(j);
      }
    }
  }
  queue<int, list<int>> pq;
  for (int i = 0; i < n; i++) {
    dist[i][i] = 0;
    pq.push(i);
    while (!pq.empty()) {
      int u = pq.front();
      pq.pop();
      for (int v : g[u]) {
        if (dist[i][v] > dist[i][u] + 1) {
          dist[i][v] = dist[i][u] + 1;
          pq.push(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:11:7: warning: unused variable 'k' [-Wunused-variable]
   11 |   int k = sqrt(n);
      |       ^
events.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     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 19 ms 51628 KB Output is correct
2 Execution timed out 1581 ms 52708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51684 KB Output is correct
2 Correct 24 ms 51616 KB Output is correct
3 Correct 41 ms 51668 KB Output is correct
4 Correct 36 ms 51680 KB Output is correct
5 Correct 48 ms 51620 KB Output is correct
6 Correct 112 ms 52484 KB Output is correct
7 Correct 197 ms 53304 KB Output is correct
8 Correct 224 ms 54344 KB Output is correct
9 Correct 1140 ms 55724 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51684 KB Output is correct
2 Correct 24 ms 51616 KB Output is correct
3 Correct 41 ms 51668 KB Output is correct
4 Correct 36 ms 51680 KB Output is correct
5 Correct 48 ms 51620 KB Output is correct
6 Correct 112 ms 52484 KB Output is correct
7 Correct 197 ms 53304 KB Output is correct
8 Correct 224 ms 54344 KB Output is correct
9 Correct 1140 ms 55724 KB Output is correct
10 Correct 21 ms 51564 KB Output is correct
11 Correct 27 ms 51668 KB Output is correct
12 Correct 41 ms 51688 KB Output is correct
13 Correct 34 ms 51624 KB Output is correct
14 Correct 43 ms 51640 KB Output is correct
15 Correct 79 ms 52476 KB Output is correct
16 Correct 211 ms 53304 KB Output is correct
17 Correct 241 ms 54340 KB Output is correct
18 Correct 1273 ms 55708 KB Output is correct
19 Execution timed out 1584 ms 81468 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51684 KB Output is correct
2 Correct 24 ms 51616 KB Output is correct
3 Correct 41 ms 51668 KB Output is correct
4 Correct 36 ms 51680 KB Output is correct
5 Correct 48 ms 51620 KB Output is correct
6 Correct 112 ms 52484 KB Output is correct
7 Correct 197 ms 53304 KB Output is correct
8 Correct 224 ms 54344 KB Output is correct
9 Correct 1140 ms 55724 KB Output is correct
10 Correct 20 ms 51668 KB Output is correct
11 Correct 20 ms 51672 KB Output is correct
12 Correct 43 ms 51692 KB Output is correct
13 Correct 40 ms 51668 KB Output is correct
14 Correct 45 ms 51684 KB Output is correct
15 Correct 80 ms 52576 KB Output is correct
16 Correct 189 ms 53300 KB Output is correct
17 Correct 222 ms 54340 KB Output is correct
18 Correct 1098 ms 55712 KB Output is correct
19 Execution timed out 1582 ms 52756 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 1580 ms 52804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51628 KB Output is correct
2 Execution timed out 1581 ms 52708 KB Time limit exceeded
3 Halted 0 ms 0 KB -