oj.uz

Submission #721898

# Submission time Handle Problem Language Result Execution time Memory
721898 2023-04-11T08:36:35 Z The_Samurai Event Hopping (BOI22_events) C++17
0 / 100
 117 ms 8392 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);
    if (n < 1000) {
        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);
                }
            }
//            cout << i << " -> ";
//            for (int u : g[i]) cout << u << ' ';
//            cout << '\n';
        }
        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';
        }
        return;
    }
    vector<int> id(n + 1);
    for (int i = 0; i < n; i++)
        id[a[i].i] = i;
    vector<pair<int, int>> ind(n, {-1, -1});
    int cnt = 0;
    auto get = [&](int u) {
        for (int i = max(u - 2, 0); i < min(n, u + 2); i++) {
            if (i == u) continue;
            if (a[i].l <= a[u].r and a[u].r <= a[i].r) return i;
        }
        return -1;
    };
    for (int i = 0; i < n; i++) {
        if (ind[i].first != -1) continue;
        ind[i] = {cnt, 0};
        int j = i, k = get(i);
        int now = 1;
        set<int> way = {-1, i};
        while (!way.count(k)) {
            way.insert(j);
            j = k;
            k = get(j);
            ind[j] = {cnt, now};
            now++;
        }
    }
    while (q--) {
        int si, ei;
        cin >> si >> ei;
        si = id[si];
        ei = id[ei];
        if (get(si) == ei) {
            cout << "1\n";
        } else if (si == ei) {
            cout << "0\n";
        } else if (ind[si].first == ind[ei].first and ind[si].second < ind[ei].second) {
            cout << ind[ei].second - ind[si].second + 1 << '\n';
        } else {
            cout << "impossible\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 0 ms 212 KB Output is correct
2 Incorrect 98 ms 8392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 8016 KB Output isn't correct
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 Incorrect 98 ms 8392 KB Output isn't correct
3 Halted 0 ms 0 KB -