oj.uz

Submission #659826

# Submission time Handle Problem Language Result Execution time Memory
659826 2022-11-19T11:36:15 Z 600Mihnea Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 3564 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
int n;
int q;

struct T {
  int l;
  int r;
};

T v[N];
int dp[N];

int main() {
  if (!home) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen("input.txt", "r", stdin);
  }

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].l >> v[i].r;
  }
  for (int iq = 1; iq <= q; iq++) {
    int ff, ss;
    cin >> ff >> ss;
    for (int i = 1; i <= n; i++) {
      dp[i] = -1;
    }
    queue<int> q;
    q.push(ff);
    dp[ff] = 0;
    while (!q.empty()) {
      int a = q.front();
      q.pop();
      for (int b = 1; b <= n; b++) {
        if (v[b].l <= v[a].r && v[a].r <= v[b].r && dp[b] == -1) {
          dp[b] = 1 + dp[a];
          q.push(b);
        }
      }
    }
    if (dp[ss] == -1) {
      cout << "impossible\n";
      continue;
    }
    cout << dp[ss] << "\n";
  }

  return 0;
}
/**

**/

Compilation message

events.cpp: In function 'int main()':
events.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1565 ms 3564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 358 ms 340 KB Output is correct
4 Correct 87 ms 340 KB Output is correct
5 Correct 175 ms 340 KB Output is correct
6 Correct 121 ms 340 KB Output is correct
7 Correct 210 ms 344 KB Output is correct
8 Correct 192 ms 344 KB Output is correct
9 Correct 277 ms 340 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 358 ms 340 KB Output is correct
4 Correct 87 ms 340 KB Output is correct
5 Correct 175 ms 340 KB Output is correct
6 Correct 121 ms 340 KB Output is correct
7 Correct 210 ms 344 KB Output is correct
8 Correct 192 ms 344 KB Output is correct
9 Correct 277 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 362 ms 340 KB Output is correct
13 Correct 85 ms 344 KB Output is correct
14 Correct 175 ms 340 KB Output is correct
15 Correct 119 ms 340 KB Output is correct
16 Correct 214 ms 360 KB Output is correct
17 Correct 193 ms 352 KB Output is correct
18 Correct 278 ms 348 KB Output is correct
19 Execution timed out 1580 ms 604 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 358 ms 340 KB Output is correct
4 Correct 87 ms 340 KB Output is correct
5 Correct 175 ms 340 KB Output is correct
6 Correct 121 ms 340 KB Output is correct
7 Correct 210 ms 344 KB Output is correct
8 Correct 192 ms 344 KB Output is correct
9 Correct 277 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 361 ms 340 KB Output is correct
13 Correct 86 ms 340 KB Output is correct
14 Correct 177 ms 340 KB Output is correct
15 Correct 120 ms 340 KB Output is correct
16 Correct 212 ms 340 KB Output is correct
17 Correct 191 ms 340 KB Output is correct
18 Correct 278 ms 340 KB Output is correct
19 Execution timed out 1576 ms 3404 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 1572 ms 3544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1565 ms 3564 KB Time limit exceeded
3 Halted 0 ms 0 KB -