oj.uz

Submission #720721

# Submission time Handle Problem Language Result Execution time Memory
720721 2023-04-09T06:27:43 Z NeroZein Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 177208 KB 
#include <bits/stdc++.h>
using namespace std;

const int Log = 18; 
const int N = 5003;

int dis[N][N];
int l[N], r[N];
vector<int> g[N]; 

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
  }
  auto intersect = [&](int x, int i, int j) {
    return x >= i && x <= j;
  };
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (intersect(r[i], l[j], r[j])) {
        g[i].push_back(j); 
      }
    }
  }  
  memset(dis, -1, sizeof dis); 
  auto Bfs = [&](int src) {
    queue<int> que;
    que.push(src); 
    dis[src][src] = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop(); 
      for (int u : g[v]) {
        if (dis[src][u] == -1) {
          dis[src][u] = dis[src][v] + 1;
          que.push(u); 
        }
      }
    }
  }; 
  for (int i = 1; i <= n; ++i) {
    Bfs(i);
    // cout << "v : " << i << '\n';
    // for (int j = 1; j <= n; ++j) {
    //   cout << dis[i][j] << ' ';
    // }
    // cout << '\n';
  }
  while (q--) {
    int u, v;
    cin >> u >> v;
    if (dis[u][v] == -1) {
      cout << "impossible" << '\n';
    } else {
      cout << dis[u][v] << '\n';
    }
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98372 KB Output is correct
2 Execution timed out 1580 ms 175952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98336 KB Output is correct
2 Correct 40 ms 98396 KB Output is correct
3 Correct 54 ms 98384 KB Output is correct
4 Correct 47 ms 98372 KB Output is correct
5 Correct 52 ms 98376 KB Output is correct
6 Correct 89 ms 99232 KB Output is correct
7 Correct 216 ms 100052 KB Output is correct
8 Correct 201 ms 101056 KB Output is correct
9 Correct 907 ms 102520 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98336 KB Output is correct
2 Correct 40 ms 98396 KB Output is correct
3 Correct 54 ms 98384 KB Output is correct
4 Correct 47 ms 98372 KB Output is correct
5 Correct 52 ms 98376 KB Output is correct
6 Correct 89 ms 99232 KB Output is correct
7 Correct 216 ms 100052 KB Output is correct
8 Correct 201 ms 101056 KB Output is correct
9 Correct 907 ms 102520 KB Output is correct
10 Correct 38 ms 98344 KB Output is correct
11 Correct 39 ms 98360 KB Output is correct
12 Correct 63 ms 98388 KB Output is correct
13 Correct 64 ms 98368 KB Output is correct
14 Correct 66 ms 98424 KB Output is correct
15 Correct 95 ms 99128 KB Output is correct
16 Correct 184 ms 100044 KB Output is correct
17 Correct 282 ms 101128 KB Output is correct
18 Correct 950 ms 102444 KB Output is correct
19 Execution timed out 1577 ms 128604 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98336 KB Output is correct
2 Correct 40 ms 98396 KB Output is correct
3 Correct 54 ms 98384 KB Output is correct
4 Correct 47 ms 98372 KB Output is correct
5 Correct 52 ms 98376 KB Output is correct
6 Correct 89 ms 99232 KB Output is correct
7 Correct 216 ms 100052 KB Output is correct
8 Correct 201 ms 101056 KB Output is correct
9 Correct 907 ms 102520 KB Output is correct
10 Correct 38 ms 98324 KB Output is correct
11 Correct 39 ms 98312 KB Output is correct
12 Correct 56 ms 98424 KB Output is correct
13 Correct 62 ms 98376 KB Output is correct
14 Correct 55 ms 98440 KB Output is correct
15 Correct 83 ms 99276 KB Output is correct
16 Correct 176 ms 100044 KB Output is correct
17 Correct 208 ms 101196 KB Output is correct
18 Correct 945 ms 102440 KB Output is correct
19 Execution timed out 1579 ms 176780 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 177208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98372 KB Output is correct
2 Execution timed out 1580 ms 175952 KB Time limit exceeded
3 Halted 0 ms 0 KB -