oj.uz

Submission #612470

# Submission time Handle Problem Language Result Execution time Memory
612470 2022-07-29T15:36:39 Z Plurm Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 71336 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++) {
    int hsh = 0;
    for (int j = 0; j < n; j++) {
      if (i == j)
        continue;
      if (events[j].first <= events[i].second &&
          events[i].second <= events[j].second) {
        hsh *= 53;
        hsh += j;
      }
    }
    tmphsh[i] = hsh;
  }
  for (int i = 0; i < n; i++) {
    __gnu_pbds::cc_hash_table<int, short> mp;
    for (int j = 0; j < n; j++) {
      if (i == j)
        continue;
      if (events[j].first <= events[i].second &&
          events[i].second <= events[j].second) {
        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:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &s, &e);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53956 KB Output is correct
2 Correct 24 ms 54032 KB Output is correct
3 Correct 41 ms 54928 KB Output is correct
4 Correct 34 ms 54456 KB Output is correct
5 Correct 44 ms 54916 KB Output is correct
6 Correct 87 ms 55032 KB Output is correct
7 Correct 216 ms 55820 KB Output is correct
8 Correct 253 ms 56384 KB Output is correct
9 Correct 1020 ms 57956 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53956 KB Output is correct
2 Correct 24 ms 54032 KB Output is correct
3 Correct 41 ms 54928 KB Output is correct
4 Correct 34 ms 54456 KB Output is correct
5 Correct 44 ms 54916 KB Output is correct
6 Correct 87 ms 55032 KB Output is correct
7 Correct 216 ms 55820 KB Output is correct
8 Correct 253 ms 56384 KB Output is correct
9 Correct 1020 ms 57956 KB Output is correct
10 Correct 21 ms 53972 KB Output is correct
11 Correct 26 ms 53964 KB Output is correct
12 Correct 41 ms 54936 KB Output is correct
13 Correct 36 ms 54540 KB Output is correct
14 Correct 35 ms 55000 KB Output is correct
15 Correct 90 ms 55040 KB Output is correct
16 Correct 201 ms 55776 KB Output is correct
17 Correct 270 ms 56328 KB Output is correct
18 Correct 999 ms 58172 KB Output is correct
19 Execution timed out 1580 ms 71336 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53956 KB Output is correct
2 Correct 24 ms 54032 KB Output is correct
3 Correct 41 ms 54928 KB Output is correct
4 Correct 34 ms 54456 KB Output is correct
5 Correct 44 ms 54916 KB Output is correct
6 Correct 87 ms 55032 KB Output is correct
7 Correct 216 ms 55820 KB Output is correct
8 Correct 253 ms 56384 KB Output is correct
9 Correct 1020 ms 57956 KB Output is correct
10 Correct 25 ms 54012 KB Output is correct
11 Correct 22 ms 53980 KB Output is correct
12 Correct 34 ms 54964 KB Output is correct
13 Correct 32 ms 54476 KB Output is correct
14 Correct 36 ms 54924 KB Output is correct
15 Correct 105 ms 54984 KB Output is correct
16 Correct 204 ms 55772 KB Output is correct
17 Correct 244 ms 56380 KB Output is correct
18 Correct 1081 ms 58104 KB Output is correct
19 Execution timed out 1590 ms 55072 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 1594 ms 55108 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 53972 KB Output is correct
2 Execution timed out 1590 ms 55148 KB Time limit exceeded
3 Halted 0 ms 0 KB -