Submission #1177259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177259		abdalrhman_sfar	Event Hopping (BOI22_events)	C++20	10 / 100	1599 ms	128220 KiB

events

/*
 *
 * author: AbdAlrhman_Sfar
 *
**/

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

const int N = 5000 + 5;
const int LOG = 20;

vector<vector<int>> adj;
int dist[N][N];

void bfs(int&u) {
    queue<int> q;
    q.push(u); dist[u][u] = 0;
    while (q.size()) {
        int v = q.front();
        q.pop();
        for (auto& it : adj[v]) {
            if (dist[u][it] == 6000) {
                dist[u][it] = dist[u][v] + 1;
                q.push(it);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q; cin >> n >> q;
    for (auto& it : dist) {
        for (auto& i : it)
            i = 6000;
    }
    adj.resize(n);
    vector<pair<int, int>> v(n);
    int i, j;
    for (i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
        for (j = 0; j < i; ++j) {
            if (v[i].first <= v[j].second && v[j].second <= v[i].second) adj[j].emplace_back(i);
            if (v[j].first <= v[i].second && v[i].second <= v[j].second) adj[i].emplace_back(j);
        }
    }
    for (i = 0; i < n; ++i) bfs(i);
    while (q--) {
        int u, v; cin >> u >> v; --u, --v;
        if (dist[u][v] == 6000) cout << "impossible\n";
        else cout << dist[u][v] << '\n';
    }
}

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