oj.uz

Submission #697930

# Submission time Handle Problem Language Result Execution time Memory
697930 2023-02-11T12:36:29 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 128660 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define fi first
#define se second
#define sz(x) (int)x.size()
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rrep(i, b, e) for (int i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 5e3 + 7;

int n, q, s[N], e[N];

void read() {
    cin >> n >> q;
    rep(i, 1, n) cin >> s[i] >> e[i];
}

int d[N][N];
vector<int> adj[N];
void sub3() {
    rep(i, 1, n) rep(j, 1, n) {
        if (s[j] <= e[i] && e[i] <= e[j]) {
            adj[i].push_back(j);
        }
    }

    memset(d, -1, sizeof d);
    rep(i, 1, n) {
        queue<int> q;
        q.push(i); d[i][i] = 0;
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v: adj[u]) if (d[i][v] == -1) {
                d[i][v] = d[i][u] + 1;
                q.push(v);
            }
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        (d[l][r] == -1 ? cout << "impossible\n" : cout << d[l][r] << '\n');
    }
}

void solve() {
    if (n <= 5000) sub3();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    read();
    solve();
}


/**
+ check mod (gõ đúng số), limit, kiểu dữ liệu
+ check format output
+mấy bài multitest:
    quên reset biến, mảng, (nên dùng fill, memset, v.v)
    quên xuống dòng
    precompute đầu bài
+nhập hết dữ liệu trước khi return
+xóa debug
**/

Compilation message

events.cpp: In function 'int main()':
events.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98508 KB Output is correct
2 Runtime error 4 ms 1076 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98508 KB Output is correct
2 Correct 36 ms 98436 KB Output is correct
3 Correct 56 ms 98604 KB Output is correct
4 Correct 50 ms 98620 KB Output is correct
5 Correct 55 ms 98552 KB Output is correct
6 Correct 82 ms 99396 KB Output is correct
7 Correct 167 ms 100140 KB Output is correct
8 Correct 195 ms 101260 KB Output is correct
9 Correct 886 ms 102648 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98508 KB Output is correct
2 Correct 36 ms 98436 KB Output is correct
3 Correct 56 ms 98604 KB Output is correct
4 Correct 50 ms 98620 KB Output is correct
5 Correct 55 ms 98552 KB Output is correct
6 Correct 82 ms 99396 KB Output is correct
7 Correct 167 ms 100140 KB Output is correct
8 Correct 195 ms 101260 KB Output is correct
9 Correct 886 ms 102648 KB Output is correct
10 Correct 37 ms 98508 KB Output is correct
11 Correct 37 ms 98492 KB Output is correct
12 Correct 52 ms 98564 KB Output is correct
13 Correct 48 ms 98496 KB Output is correct
14 Correct 53 ms 98592 KB Output is correct
15 Correct 81 ms 99476 KB Output is correct
16 Correct 167 ms 100184 KB Output is correct
17 Correct 192 ms 101260 KB Output is correct
18 Correct 874 ms 102696 KB Output is correct
19 Execution timed out 1583 ms 128660 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98508 KB Output is correct
2 Correct 36 ms 98436 KB Output is correct
3 Correct 56 ms 98604 KB Output is correct
4 Correct 50 ms 98620 KB Output is correct
5 Correct 55 ms 98552 KB Output is correct
6 Correct 82 ms 99396 KB Output is correct
7 Correct 167 ms 100140 KB Output is correct
8 Correct 195 ms 101260 KB Output is correct
9 Correct 886 ms 102648 KB Output is correct
10 Correct 37 ms 98504 KB Output is correct
11 Correct 37 ms 98532 KB Output is correct
12 Correct 53 ms 98500 KB Output is correct
13 Correct 48 ms 98564 KB Output is correct
14 Correct 51 ms 98560 KB Output is correct
15 Correct 82 ms 99388 KB Output is correct
16 Correct 166 ms 100156 KB Output is correct
17 Correct 197 ms 101260 KB Output is correct
18 Correct 898 ms 102608 KB Output is correct
19 Runtime error 3 ms 1080 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98508 KB Output is correct
2 Runtime error 4 ms 1076 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -