oj.uz

Submission #721580

# Submission time Handle Problem Language Result Execution time Memory
721580 2023-04-11T04:55:09 Z The_Samurai Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 524288 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

struct node {
    int l, r, i;
};

bool comp(node a, node b) {
    if (a.r < b.r) return true;
    if (a.r > b.r) return false;
    return a.l < b.l;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<node> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].i = i + 1;
    }
    sort(a.begin(), a.end(), comp);
    vector<int> ind(n + 1);
    for (int i = 0; i < n; i++) {
        ind[a[i].i] = i;
    }
    vector<vector<int>> can(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[j].l <= a[i].r and a[i].r <= a[j].r) {
                g[i].emplace_back(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        can[i][i] = 0;
        queue<int> pq;
        pq.push(i);
        while (!pq.empty()) {
            int u = pq.front();
            pq.pop();
            for (int v : g[u]) {
                if (can[i][v] == -1) {
                    can[i][v] = can[i][u] + 1;
                    pq.push(v);
                }
            }
        }
    }
    while (q--) {
        int si, ei;
        cin >> si >> ei;
        si = ind[si];
        ei = ind[ei];
        if (can[si][ei] == -1) cout << "impossible";
        else cout << can[si][ei];
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 253 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 10 ms 4360 KB Output is correct
4 Correct 10 ms 4276 KB Output is correct
5 Correct 12 ms 4240 KB Output is correct
6 Correct 75 ms 5128 KB Output is correct
7 Correct 198 ms 5932 KB Output is correct
8 Correct 218 ms 6968 KB Output is correct
9 Correct 1364 ms 8332 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 10 ms 4360 KB Output is correct
4 Correct 10 ms 4276 KB Output is correct
5 Correct 12 ms 4240 KB Output is correct
6 Correct 75 ms 5128 KB Output is correct
7 Correct 198 ms 5932 KB Output is correct
8 Correct 218 ms 6968 KB Output is correct
9 Correct 1364 ms 8332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 10 ms 4308 KB Output is correct
13 Correct 7 ms 4328 KB Output is correct
14 Correct 12 ms 4292 KB Output is correct
15 Correct 60 ms 5124 KB Output is correct
16 Correct 205 ms 5928 KB Output is correct
17 Correct 214 ms 6988 KB Output is correct
18 Correct 1392 ms 8336 KB Output is correct
19 Execution timed out 1584 ms 128172 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 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 10 ms 4360 KB Output is correct
4 Correct 10 ms 4276 KB Output is correct
5 Correct 12 ms 4240 KB Output is correct
6 Correct 75 ms 5128 KB Output is correct
7 Correct 198 ms 5932 KB Output is correct
8 Correct 218 ms 6968 KB Output is correct
9 Correct 1364 ms 8332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 12 ms 4360 KB Output is correct
13 Correct 9 ms 4296 KB Output is correct
14 Correct 11 ms 4308 KB Output is correct
15 Correct 56 ms 5076 KB Output is correct
16 Correct 202 ms 5932 KB Output is correct
17 Correct 246 ms 7084 KB Output is correct
18 Correct 1273 ms 8372 KB Output is correct
19 Runtime error 275 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 255 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 253 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -