oj.uz

Submission #604429

# Submission time Handle Problem Language Result Execution time Memory
604429 2022-07-25T06:22:35 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 43424 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(E[i], S[i]);
        }

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

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

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

            int ps = lower_bound(vec.begin(), vec.end(), make_pair(e, s)) - vec.begin();
            int pe = lower_bound(vec.begin(), vec.end(), make_pair(e, s)) - 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 54 ms 4880 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 2 ms 2644 KB Output is correct
3 Correct 17 ms 10580 KB Output is correct
4 Correct 14 ms 10636 KB Output is correct
5 Correct 19 ms 10572 KB Output is correct
6 Correct 45 ms 11396 KB Output is correct
7 Correct 129 ms 12256 KB Output is correct
8 Correct 142 ms 13236 KB Output is correct
9 Correct 722 ms 14636 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 2 ms 2644 KB Output is correct
3 Correct 17 ms 10580 KB Output is correct
4 Correct 14 ms 10636 KB Output is correct
5 Correct 19 ms 10572 KB Output is correct
6 Correct 45 ms 11396 KB Output is correct
7 Correct 129 ms 12256 KB Output is correct
8 Correct 142 ms 13236 KB Output is correct
9 Correct 722 ms 14636 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 12 ms 10652 KB Output is correct
14 Correct 18 ms 10616 KB Output is correct
15 Correct 45 ms 11388 KB Output is correct
16 Correct 139 ms 12356 KB Output is correct
17 Correct 141 ms 13224 KB Output is correct
18 Correct 738 ms 14552 KB Output is correct
19 Execution timed out 1568 ms 43424 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 2 ms 2644 KB Output is correct
3 Correct 17 ms 10580 KB Output is correct
4 Correct 14 ms 10636 KB Output is correct
5 Correct 19 ms 10572 KB Output is correct
6 Correct 45 ms 11396 KB Output is correct
7 Correct 129 ms 12256 KB Output is correct
8 Correct 142 ms 13236 KB Output is correct
9 Correct 722 ms 14636 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 17 ms 10672 KB Output is correct
13 Correct 13 ms 10580 KB Output is correct
14 Correct 18 ms 10620 KB Output is correct
15 Correct 45 ms 11340 KB Output is correct
16 Correct 118 ms 12244 KB Output is correct
17 Correct 141 ms 13264 KB Output is correct
18 Correct 722 ms 14552 KB Output is correct
19 Incorrect 27 ms 4648 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4892 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 54 ms 4880 KB Output isn't correct
3 Halted 0 ms 0 KB -