oj.uz

Submission #714290

# Submission time Handle Problem Language Result Execution time Memory
714290 2023-03-24T08:01:32 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 398908 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(vv(int)) dist(MAX , vv(int) (MAX , -1));

void BFS(int node){
    dist[node][node] = 0;
    queue<int> Q;   
    Q.push(node);
    while(!Q.empty()){
        int from = Q.front();
        Q.pop();
        for(auto to : g[from]){
            if(dist[node][to] == -1){
                dist[node][to] = dist[node][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<n ; i++){
        BFS(i);
    }
    //cout << dist[0][3] << ln;
    for(int i=0 ; i<q ; i++){
        int u , v;
        cin >> u >> v;
        u--; v--;
        if(dist[u][v] == -1){
            cout << "impossible" << ln;
        }
        else{
            cout << dist[u][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 78 ms 196752 KB Output is correct
2 Runtime error 292 ms 398700 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 86 ms 196720 KB Output is correct
2 Correct 81 ms 196780 KB Output is correct
3 Correct 97 ms 196700 KB Output is correct
4 Correct 102 ms 196684 KB Output is correct
5 Correct 96 ms 196724 KB Output is correct
6 Correct 135 ms 198244 KB Output is correct
7 Correct 252 ms 200000 KB Output is correct
8 Correct 289 ms 202108 KB Output is correct
9 Correct 1236 ms 204884 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 196720 KB Output is correct
2 Correct 81 ms 196780 KB Output is correct
3 Correct 97 ms 196700 KB Output is correct
4 Correct 102 ms 196684 KB Output is correct
5 Correct 96 ms 196724 KB Output is correct
6 Correct 135 ms 198244 KB Output is correct
7 Correct 252 ms 200000 KB Output is correct
8 Correct 289 ms 202108 KB Output is correct
9 Correct 1236 ms 204884 KB Output is correct
10 Correct 81 ms 196716 KB Output is correct
11 Correct 79 ms 196656 KB Output is correct
12 Correct 91 ms 196752 KB Output is correct
13 Correct 92 ms 196852 KB Output is correct
14 Correct 98 ms 196724 KB Output is correct
15 Correct 134 ms 198436 KB Output is correct
16 Correct 258 ms 200020 KB Output is correct
17 Correct 320 ms 202192 KB Output is correct
18 Correct 1307 ms 204876 KB Output is correct
19 Execution timed out 1595 ms 251144 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 196720 KB Output is correct
2 Correct 81 ms 196780 KB Output is correct
3 Correct 97 ms 196700 KB Output is correct
4 Correct 102 ms 196684 KB Output is correct
5 Correct 96 ms 196724 KB Output is correct
6 Correct 135 ms 198244 KB Output is correct
7 Correct 252 ms 200000 KB Output is correct
8 Correct 289 ms 202108 KB Output is correct
9 Correct 1236 ms 204884 KB Output is correct
10 Correct 83 ms 196656 KB Output is correct
11 Correct 87 ms 196752 KB Output is correct
12 Correct 94 ms 196684 KB Output is correct
13 Correct 102 ms 196892 KB Output is correct
14 Correct 95 ms 196788 KB Output is correct
15 Correct 141 ms 198376 KB Output is correct
16 Correct 245 ms 200012 KB Output is correct
17 Correct 307 ms 202060 KB Output is correct
18 Correct 1219 ms 204804 KB Output is correct
19 Runtime error 255 ms 398748 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 247 ms 398908 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 78 ms 196752 KB Output is correct
2 Runtime error 292 ms 398700 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -