Submission #746017

#	Time	Username	Problem	Language	Result	Execution time	Memory
746017		vjudge1	Event Hopping (BOI22_events)	C++17	0 / 100	1597 ms	302296 KiB

events

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

struct Event {
    int S;
    int E;
    int i;
};
bool operator<(Event A, Event B) {
    return A.S<B.S;
}
int N, a, b, Q;
map<int, set<Event>> vegek;
vector<int> evts;
vector<int> starts;
map<int, vector<int>> graf;
vector<int> hely;
map<int, map<int, int>> tav;
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>N>>Q;
    hely.resize(N+1);
    for(int i=0; i<N; i++) {
        cin>>a>>b;
        starts.pb(a);
        if(vegek.find(b)==vegek.end()) {
            evts.pb(b);
        }
        vegek[b].insert({a, b, i+1});
    }
    sort(evts.begin(), evts.end(), [](int a, int b) {return vegek[a].begin()->S<vegek[b].begin()->S;});
    for(int i=0; i<N; i++) {
        for(const Event &evt : vegek[evts[i]]) hely[evt.i]=evts[i];
        for(int j=i+1; j<N&&vegek[evts[j]].begin()->S<=vegek[evts[i]].begin()->E; j++) {
            if(vegek[evts[j]].begin()->E<vegek[evts[i]].begin()->E) continue;
            graf[evts[j]].pb(evts[i]);
        }
    }
    for(int i=0; i<N; i++) {
        tav[evts[i]][evts[i]]=0;
    }
    for(int i=0; i<N; i++) {
        int x=evts[i];
        for(int be : graf[x]) {
            for(auto &beBe : tav[be]) {
                if(tav[x].find(beBe.first)!=tav[x].end()) {
                    if(tav[x][beBe.first]>beBe.second+1) {
                        tav[x][beBe.first]=beBe.second+1;
                        //honnan[x][beBe.first]=be;
                    }
                }
                else {
                    tav[x][beBe.first]=beBe.second+1;
                    //honnan[x][beBe.first]=be;
                }
            }
        }
    }
    for(int i=0;i<Q;i++){
        cin>>a>>b;
        auto it = tav[hely[b]].find(hely[a]);
        if(it==tav[hely[b]].end()) {
            cout<<"impossible\n";
        }
        else  {
            //cout<<"x"<<vegek[hely[b]].begin()->S<<"y"<<starts[b-1]<<endl;
            if(starts[b-1]==vegek[hely[b]].begin()->S) {
            cout<<it->second<<'\n';
        }
        else {
            cout<<it->second+1<<"\n";
        }
        }
    }
}

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