oj.uz

Submission #714287

# Submission time Handle Problem Language Result Execution time Memory
714287 2023-03-24T07:55:49 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 55060 KB 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define ll          long long 
#define ull         unsigned long long 
#define ld          long double 
#define ui          unsigned int 
#define f           first
#define s           second
#define ins         insert
#define pb          push_back
#define mp          make_pair
#define ln          '\n'
#define int         ll
#define pii         pair<int , int> 
#define INF         LLONG_MAX
#define vv(a)       vector<a>
#define pp(a, b)    pair<a, b>
#define pq(a)       priority_queue<a>
#define qq(a)       queue<a>
#define ss(a)       set<a>
#define mss(a)      multiset<a>
#define mm(a, b)    map<a, b>
#define mmm(a , b)  multimap<a , b>
#define sz(x)       (x).size()
#define all(x)      (x).begin() , (x).end()
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

const int MAX = 5005;
vv(pii) a(MAX);
vv(vv(int)) g(MAX);
vv(int) dist(MAX);

void init(){
    for(int i=0 ; i<MAX ; i++){
        dist[i] = -1;
    }
}

void BFS(int node){
    queue<int> Q;
    Q.push(node);
    while(!Q.empty()){
        int from = Q.front();
        Q.pop();
        for(auto to : g[from]){
            if(dist[to] == -1){
                dist[to] = dist[from] + 1;
                Q.push(to);
            }
        }
    }
}

void solve(){
    int n , q;
    cin >> n >> q;
    for(int i=0 ; i<n ; i++){
        cin >> a[i].f >> a[i].s;
    }   
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<n ; j++){
            if(i != j){
                if(a[j].f <= a[i].s && a[j].s >= a[i].s){
                    g[i].pb(j);
                }
            }
        }
    }
    for(int i=0 ; i<q ; i++){
        int u , v;
        cin >> u >> v;
        u--; v--;
        init();
        dist[u] = 0;
        BFS(u);
        if(dist[v] == -1){
            cout << "impossible" << ln;
        }
        else{
            cout << dist[v] << ln;
        }
    }
}


signed main(){
    fastio

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 6 ms 1068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 8 ms 560 KB Output is correct
4 Correct 6 ms 584 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 13 ms 2132 KB Output is correct
7 Correct 28 ms 3888 KB Output is correct
8 Correct 25 ms 5844 KB Output is correct
9 Correct 101 ms 8488 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 8 ms 560 KB Output is correct
4 Correct 6 ms 584 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 13 ms 2132 KB Output is correct
7 Correct 28 ms 3888 KB Output is correct
8 Correct 25 ms 5844 KB Output is correct
9 Correct 101 ms 8488 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 556 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 6 ms 596 KB Output is correct
14 Correct 8 ms 596 KB Output is correct
15 Correct 12 ms 2180 KB Output is correct
16 Correct 30 ms 3808 KB Output is correct
17 Correct 25 ms 5912 KB Output is correct
18 Correct 102 ms 8592 KB Output is correct
19 Execution timed out 1580 ms 55060 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 8 ms 560 KB Output is correct
4 Correct 6 ms 584 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 13 ms 2132 KB Output is correct
7 Correct 28 ms 3888 KB Output is correct
8 Correct 25 ms 5844 KB Output is correct
9 Correct 101 ms 8488 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 560 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 5 ms 564 KB Output is correct
14 Correct 7 ms 580 KB Output is correct
15 Correct 14 ms 2124 KB Output is correct
16 Correct 23 ms 3796 KB Output is correct
17 Correct 24 ms 5844 KB Output is correct
18 Correct 107 ms 8532 KB Output is correct
19 Runtime error 7 ms 1072 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 6 ms 1068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -