Submission #746017

#TimeUsernameProblemLanguageResultExecution timeMemory
746017vjudge1Event Hopping (BOI22_events)C++17
0 / 100
1597 ms302296 KiB
#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"; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...