제출 #745791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745791		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	94 ms	17408 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> > components;
vector<pair<int, int>> pos;


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

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

void dfs(int x, int ind) {
    components[ind].push_back(x);
    pos[x] = {ind, components[ind].size()};

    for(int sz : g[x]) dfs(sz, ind);
}

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);
    pos.resize(n+1);
    vector<Event > events;
    for(int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        events.push_back({x, y, i+1});
    }


    sort(events.begin(), events.end());
    vector<int> be(n+1, 0);

    for(int i = 0; i < n-1; i++) {
        if(events[i].e >= events[i+1].s && events[i].e <= events[i+1].e) {
            g[events[i].ind].push_back(events[i+1].ind);
            be[events[i+1].ind]++;
        }
    }

    for(int i = 1; i <= n; i++) {
        if(be[i] == 0) {
            components.push_back({});
            dfs(i, components.size()-1);
        }
    }

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

        if(pos[x].first == pos[y].first && pos[x].second < pos[y].second) cout << pos[y].second - pos[x].second << "\n";
        else cout << "impossible\n";
    }

    return 0;
}

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