oj.uz

Submission #604350

# Submission time Handle Problem Language Result Execution time Memory
604350 2022-07-25T04:29:21 Z Plurm Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 81488 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> 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 24 ms 51532 KB Output is correct
2 Execution timed out 1572 ms 52716 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 51668 KB Output is correct
2 Correct 19 ms 51652 KB Output is correct
3 Correct 33 ms 51680 KB Output is correct
4 Correct 27 ms 51668 KB Output is correct
5 Correct 32 ms 51696 KB Output is correct
6 Correct 102 ms 52468 KB Output is correct
7 Correct 233 ms 53324 KB Output is correct
8 Correct 288 ms 54328 KB Output is correct
9 Correct 1487 ms 55684 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51668 KB Output is correct
2 Correct 19 ms 51652 KB Output is correct
3 Correct 33 ms 51680 KB Output is correct
4 Correct 27 ms 51668 KB Output is correct
5 Correct 32 ms 51696 KB Output is correct
6 Correct 102 ms 52468 KB Output is correct
7 Correct 233 ms 53324 KB Output is correct
8 Correct 288 ms 54328 KB Output is correct
9 Correct 1487 ms 55684 KB Output is correct
10 Correct 22 ms 51668 KB Output is correct
11 Correct 19 ms 51624 KB Output is correct
12 Correct 32 ms 51632 KB Output is correct
13 Correct 28 ms 51696 KB Output is correct
14 Correct 32 ms 51640 KB Output is correct
15 Correct 91 ms 52468 KB Output is correct
16 Correct 246 ms 53228 KB Output is correct
17 Correct 274 ms 54336 KB Output is correct
18 Correct 1486 ms 55688 KB Output is correct
19 Execution timed out 1595 ms 81488 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 51668 KB Output is correct
2 Correct 19 ms 51652 KB Output is correct
3 Correct 33 ms 51680 KB Output is correct
4 Correct 27 ms 51668 KB Output is correct
5 Correct 32 ms 51696 KB Output is correct
6 Correct 102 ms 52468 KB Output is correct
7 Correct 233 ms 53324 KB Output is correct
8 Correct 288 ms 54328 KB Output is correct
9 Correct 1487 ms 55684 KB Output is correct
10 Correct 19 ms 51668 KB Output is correct
11 Correct 18 ms 51636 KB Output is correct
12 Correct 33 ms 51688 KB Output is correct
13 Correct 28 ms 51672 KB Output is correct
14 Correct 33 ms 51624 KB Output is correct
15 Correct 85 ms 52428 KB Output is correct
16 Correct 227 ms 53280 KB Output is correct
17 Correct 304 ms 54332 KB Output is correct
18 Correct 1465 ms 55688 KB Output is correct
19 Execution timed out 1556 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 1590 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 24 ms 51532 KB Output is correct
2 Execution timed out 1572 ms 52716 KB Time limit exceeded
3 Halted 0 ms 0 KB -