oj.uz

Submission #604355

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

vector<int> g[100005];
short dist[5005][5005];
int fastqueue[5000005];
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;
  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);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    dist[i][i] = 0;
    fastqueue[tidx++] = i;
    while (hidx != tidx) {
      int u = fastqueue[hidx++];
      for (int 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:14:7: warning: unused variable 'k' [-Wunused-variable]
   14 |   int k = sqrt(n);
      |       ^
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:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~
events.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51552 KB Output is correct
2 Execution timed out 1593 ms 52772 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 51592 KB Output is correct
2 Correct 22 ms 51612 KB Output is correct
3 Correct 31 ms 53644 KB Output is correct
4 Correct 29 ms 52584 KB Output is correct
5 Correct 32 ms 53580 KB Output is correct
6 Correct 75 ms 53636 KB Output is correct
7 Correct 239 ms 55240 KB Output is correct
8 Correct 229 ms 56464 KB Output is correct
9 Correct 1074 ms 59564 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51592 KB Output is correct
2 Correct 22 ms 51612 KB Output is correct
3 Correct 31 ms 53644 KB Output is correct
4 Correct 29 ms 52584 KB Output is correct
5 Correct 32 ms 53580 KB Output is correct
6 Correct 75 ms 53636 KB Output is correct
7 Correct 239 ms 55240 KB Output is correct
8 Correct 229 ms 56464 KB Output is correct
9 Correct 1074 ms 59564 KB Output is correct
10 Correct 20 ms 51668 KB Output is correct
11 Correct 20 ms 51668 KB Output is correct
12 Correct 31 ms 53596 KB Output is correct
13 Correct 28 ms 52596 KB Output is correct
14 Correct 34 ms 53648 KB Output is correct
15 Correct 71 ms 53708 KB Output is correct
16 Correct 210 ms 55244 KB Output is correct
17 Correct 203 ms 56256 KB Output is correct
18 Correct 1028 ms 59636 KB Output is correct
19 Execution timed out 1581 ms 85648 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 51592 KB Output is correct
2 Correct 22 ms 51612 KB Output is correct
3 Correct 31 ms 53644 KB Output is correct
4 Correct 29 ms 52584 KB Output is correct
5 Correct 32 ms 53580 KB Output is correct
6 Correct 75 ms 53636 KB Output is correct
7 Correct 239 ms 55240 KB Output is correct
8 Correct 229 ms 56464 KB Output is correct
9 Correct 1074 ms 59564 KB Output is correct
10 Correct 21 ms 51668 KB Output is correct
11 Correct 18 ms 51668 KB Output is correct
12 Correct 33 ms 53588 KB Output is correct
13 Correct 32 ms 52620 KB Output is correct
14 Correct 32 ms 53588 KB Output is correct
15 Correct 74 ms 53664 KB Output is correct
16 Correct 181 ms 55152 KB Output is correct
17 Correct 198 ms 56224 KB Output is correct
18 Correct 1022 ms 59640 KB Output is correct
19 Execution timed out 1578 ms 52800 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 1569 ms 52812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51552 KB Output is correct
2 Execution timed out 1593 ms 52772 KB Time limit exceeded
3 Halted 0 ms 0 KB -