Submission #589027

#	Time	Username	Problem	Language	Result	Execution time	Memory
589027		1zaid1	Event Hopping (BOI22_events)	C++14	10 / 100	1578 ms	2800 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int M = 1e4+2;
struct rng {int l, r, i;};
int dist[M];

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, p;
    cin >> n >> p;

    vector<rng> v(n);
    for (auto &[l, r, i]:v) cin >> l >> r;
    for (int i = 0; i < n; i++) v[i].i = i;

    bitset<100005> vis;
    while (p--) {
        int a, b;
        cin >> a >> b; a--; b--;
        if (a == b) {
            cout << 0 << endl;
            continue;
        }

        vis[a] = 1;
        queue<rng> q;
        q.push(v[a]);
        while (!q.empty()) {
            // cout << q << "I: "<< cr.i+1 << endl;
            rng t = q.front(); q.pop();
            for (auto [l, r, i]:v) {
                if (!vis[i]) {
                    if (l <= t.r && t.r <= r) {
                        vis[i] = 1;
                        dist[i] = dist[t.i]+1;
                        q.push({l, r, i});
                    }
                }
            }
        }

        if (vis[b]) {
            cout << dist[b] << endl;
        } else {
            cout << "impossible" << endl;
        } vis = 0;

        for (int i = 0; i <= n; i++) dist[i] = 0;
    }

    return 0;
}
/*
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2
*/

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:16:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for (auto &[l, r, i]:v) cin >> l >> r;
      |                ^
events.cpp:34:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             for (auto [l, r, i]:v) {
      |                       ^

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30