Submission #745775

#	Time	Username	Problem	Language	Result	Execution time	Memory
745775		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1565 ms	524288 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

vector<vector<int> > g;

vector<vector<int> > dist;
vector<pair<int, int>> pos;


struct Event {
    int s,e, ind;
};

bool operator<(Event &a, Event &b) {
    if(a.s == b.s) return a.e < b.e;
    return a.s < b.s;
}

int main() {

/*#ifndef ONLINE_JUDGE
   freopen("../../input.txt", "r", stdin);
   freopen("../../output.txt", "w", stdout);
#endif*/
   InTheNameOfGod;

    int n,q;
    cin >> n >> q;

    g.resize(n+1);
    dist.resize(n+1, vector<int>(n+1, -1));
    vector<Event > v;
    for(int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        v.push_back({x, y, i+1});
    }


    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)  {
            if(i == j) continue;

            if(v[i].e >= v[j].s && v[i].e <= v[j].e) {
                g[i+1].push_back(j+1);
            }
        }
    }

    for(int i = 1; i <= n; i++)  {
        queue<int> q;
        q.push(i);
        dist[i][i] = 0;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            for(int sz : g[cur]) {
                if(dist[i][sz] != -1) continue;
                dist[i][sz] = dist[i][cur] + 1;
                q.push(sz);
            }
        }
    }

    while(q--)  {
        int x,y;
        cin >> x >> y;

        if(dist[x][y] == -1) cout <<  "impossible\n";
        else cout << dist[x][y] << "\n";
    }

    return 0;
}

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