oj.uz

Submission #604427

# Submission time Handle Problem Language Result Execution time Memory
604427 2022-07-25T06:20:40 Z Jomnoi Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 43524 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());

        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 53 ms 4904 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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 18 ms 10660 KB Output is correct
4 Correct 14 ms 10648 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11328 KB Output is correct
7 Correct 119 ms 12220 KB Output is correct
8 Correct 138 ms 13288 KB Output is correct
9 Correct 734 ms 14624 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 18 ms 10660 KB Output is correct
4 Correct 14 ms 10648 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11328 KB Output is correct
7 Correct 119 ms 12220 KB Output is correct
8 Correct 138 ms 13288 KB Output is correct
9 Correct 734 ms 14624 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 16 ms 10580 KB Output is correct
13 Correct 13 ms 10752 KB Output is correct
14 Correct 18 ms 10656 KB Output is correct
15 Correct 45 ms 11364 KB Output is correct
16 Correct 120 ms 12192 KB Output is correct
17 Correct 140 ms 13316 KB Output is correct
18 Correct 728 ms 14552 KB Output is correct
19 Execution timed out 1588 ms 43524 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 18 ms 10660 KB Output is correct
4 Correct 14 ms 10648 KB Output is correct
5 Correct 18 ms 10580 KB Output is correct
6 Correct 48 ms 11328 KB Output is correct
7 Correct 119 ms 12220 KB Output is correct
8 Correct 138 ms 13288 KB Output is correct
9 Correct 734 ms 14624 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 10648 KB Output is correct
13 Correct 13 ms 10600 KB Output is correct
14 Correct 18 ms 10604 KB Output is correct
15 Correct 46 ms 11388 KB Output is correct
16 Correct 118 ms 12236 KB Output is correct
17 Correct 164 ms 13288 KB Output is correct
18 Correct 738 ms 14604 KB Output is correct
19 Incorrect 29 ms 4716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 4932 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 53 ms 4904 KB Output isn't correct
3 Halted 0 ms 0 KB -