oj.uz

Submission #604386

# Submission time Handle Problem Language Result Execution time Memory
604386 2022-07-25T05:24:32 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 43832 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 5005;
const int INF = 1e9 + 7;

int S[MAX_N], E[MAX_N];
int dist[MAX_N];
int can_reach[MAX_M][MAX_M];
vector <int> graph[MAX_N];
int parent[MAX_N];

int root(int u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

void merge(int u, int v) {
    u = root(u), v = root(v);
    if(u != v) {
        parent[v] = u;
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;

    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> E[i];
    }

    if(N <= 5000) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(i != j and S[j] <= E[i] and E[i] <= E[j]) {
                    graph[i].push_back(j);
                }
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                dist[j] = -1;
            }

            queue <int> q;
            q.push(i);
            dist[i] = 0;
            while(!q.empty()) {
                int u = q.front();
                q.pop();

                for(auto v : graph[u]) {
                    if(dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }

            for(int j = 1; j <= N; j++) {
                can_reach[i][j] = dist[j];
            }
        }

        while(Q--) {
            int s, e;
            cin >> s >> e;

            if(can_reach[s][e] == -1) {
                cout << "impossible\n";
            }
            else {
                cout << can_reach[s][e] << '\n';
            }
        }
    }
    else {
        vector <pair <int, int>> vec;
        for(int i = 1; i <= N; i++) {
            vec.emplace_back(S[i], E[i]);
        }

        sort(vec.begin(), vec.end());

        for(int i = 1; i < N; i++) {
            if(vec[i].first <= vec[i - 1].second and vec[i - 1].second <= vec[i].second) {
                merge(i - 1, i);
            }
        }

        while(Q--) {
            int s, e;
            cin >> s >> e;

            int ps = lower_bound(vec.begin(), vec.end(), make_pair(s, e)) - vec.begin();
            int pe = lower_bound(vec.begin(), vec.end(), make_pair(s, e)) - vec.begin();

            if(ps <= pe and root(ps) == root(pe)) {
                cout << pe - ps << '\n';
            }
            else {
                cout << "impossible\n";
            }
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 51 ms 4928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 15 ms 10580 KB Output is correct
4 Correct 13 ms 10588 KB Output is correct
5 Correct 18 ms 10656 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 123 ms 12200 KB Output is correct
8 Correct 143 ms 13492 KB Output is correct
9 Correct 713 ms 14568 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 15 ms 10580 KB Output is correct
4 Correct 13 ms 10588 KB Output is correct
5 Correct 18 ms 10656 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 123 ms 12200 KB Output is correct
8 Correct 143 ms 13492 KB Output is correct
9 Correct 713 ms 14568 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 16 ms 10580 KB Output is correct
13 Correct 13 ms 10580 KB Output is correct
14 Correct 18 ms 10604 KB Output is correct
15 Correct 44 ms 11340 KB Output is correct
16 Correct 116 ms 12204 KB Output is correct
17 Correct 143 ms 13208 KB Output is correct
18 Correct 717 ms 14684 KB Output is correct
19 Execution timed out 1579 ms 43832 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 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 15 ms 10580 KB Output is correct
4 Correct 13 ms 10588 KB Output is correct
5 Correct 18 ms 10656 KB Output is correct
6 Correct 47 ms 11448 KB Output is correct
7 Correct 123 ms 12200 KB Output is correct
8 Correct 143 ms 13492 KB Output is correct
9 Correct 713 ms 14568 KB Output is correct
10 Correct 1 ms 2712 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 17 ms 10576 KB Output is correct
13 Correct 13 ms 10580 KB Output is correct
14 Correct 18 ms 10580 KB Output is correct
15 Correct 47 ms 11368 KB Output is correct
16 Correct 122 ms 12200 KB Output is correct
17 Correct 139 ms 13200 KB Output is correct
18 Correct 724 ms 14744 KB Output is correct
19 Incorrect 27 ms 4684 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 4900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 51 ms 4928 KB Output isn't correct
3 Halted 0 ms 0 KB -