oj.uz

Submission #746017

# Submission time Handle Problem Language Result Execution time Memory
746017 2023-05-21T10:36:45 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 302296 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1597 ms 302296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 91 ms 24332 KB Output is correct
4 Correct 47 ms 12360 KB Output is correct
5 Correct 91 ms 24104 KB Output is correct
6 Execution timed out 1577 ms 1244 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 91 ms 24332 KB Output is correct
4 Correct 47 ms 12360 KB Output is correct
5 Correct 91 ms 24104 KB Output is correct
6 Execution timed out 1577 ms 1244 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 91 ms 24332 KB Output is correct
4 Correct 47 ms 12360 KB Output is correct
5 Correct 91 ms 24104 KB Output is correct
6 Execution timed out 1577 ms 1244 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1541 ms 262236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1597 ms 302296 KB Time limit exceeded
3 Halted 0 ms 0 KB -