oj.uz

Submission #659835

# Submission time Handle Problem Language Result Execution time Memory
659835 2022-11-19T11:51:25 Z 600Mihnea Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 1464 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 nxt[N];
int ant[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 i = 1; i <= n; i++) {
    nxt[i] = -1;
    for (int j = 1; j <= n; j++) {
      if (v[j].l <= v[i].r) {
        if (nxt[i] == -1) {
          nxt[i] = j;
        } else {
          if (v[j].r > v[nxt[i]].r) {
            nxt[i] = j;
          }
        }
      }
    }
    if (nxt[i] != -1 && v[i].r >= v[nxt[i]].r) {
      nxt[i] = -1;
    }
  }
  for (int i = 1; i <= n; i++) {
    ant[i] = -1;
    for (int j = 1; j <= n; j++) {
      if (v[i].l <= v[j].r && v[j].r <= v[i].l) {
        if (ant[i] == -1) {
          ant[i] = j;
        }
      } else {
        if (v[j].l < v[ant[i]].l) {
          ant[i] = j;
        }
      }
    }
  }
  for (int iq = 1; iq <= q; iq++) {
    int ff, ss;
    cin >> ff >> ss;
    for (int i = 1; i <= n; i++) {
      dp[i] = -1;
    }
    int co = 0;
    while (nxt[ff] != -1 && v[nxt[ff]].r <= v[ss].l) {
      ff = nxt[ff];
      co++;
    }
    while (ant[ss] != -1 && v[ant[ss]].l >= v[ss].r) {
      ss = ant[ss];
      co++;
    }
    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;
    }
  ///  assert(dp[ss] <= 3);
    cout << co + dp[ss] << "\n";
  }

  return 0;
}
/**

**/

Compilation message

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

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 51 ms 364 KB Output is correct
5 Correct 186 ms 340 KB Output is correct
6 Correct 125 ms 340 KB Output is correct
7 Correct 214 ms 348 KB Output is correct
8 Correct 195 ms 344 KB Output is correct
9 Correct 287 ms 344 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 51 ms 364 KB Output is correct
5 Correct 186 ms 340 KB Output is correct
6 Correct 125 ms 340 KB Output is correct
7 Correct 214 ms 348 KB Output is correct
8 Correct 195 ms 344 KB Output is correct
9 Correct 287 ms 344 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 6 ms 356 KB Output is correct
13 Correct 51 ms 352 KB Output is correct
14 Correct 189 ms 344 KB Output is correct
15 Correct 128 ms 360 KB Output is correct
16 Correct 213 ms 348 KB Output is correct
17 Correct 194 ms 344 KB Output is correct
18 Correct 287 ms 360 KB Output is correct
19 Execution timed out 1596 ms 376 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 51 ms 364 KB Output is correct
5 Correct 186 ms 340 KB Output is correct
6 Correct 125 ms 340 KB Output is correct
7 Correct 214 ms 348 KB Output is correct
8 Correct 195 ms 344 KB Output is correct
9 Correct 287 ms 344 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 54 ms 340 KB Output is correct
14 Correct 185 ms 340 KB Output is correct
15 Correct 125 ms 340 KB Output is correct
16 Correct 224 ms 352 KB Output is correct
17 Correct 203 ms 348 KB Output is correct
18 Correct 291 ms 344 KB Output is correct
19 Execution timed out 1581 ms 1356 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 1582 ms 1448 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 340 KB Output is correct
2 Execution timed out 1588 ms 1464 KB Time limit exceeded
3 Halted 0 ms 0 KB -