oj.uz

Submission #714410

# Submission time Handle Problem Language Result Execution time Memory
714410 2023-03-24T10:36:28 Z Ferid20072020 Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 399832 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 = 5010;
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 80 ms 197144 KB Output is correct
2 Runtime error 267 ms 399832 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 81 ms 197196 KB Output is correct
2 Correct 77 ms 197184 KB Output is correct
3 Correct 92 ms 197184 KB Output is correct
4 Correct 88 ms 197196 KB Output is correct
5 Correct 105 ms 197128 KB Output is correct
6 Correct 133 ms 198736 KB Output is correct
7 Correct 242 ms 200456 KB Output is correct
8 Correct 286 ms 202592 KB Output is correct
9 Correct 1252 ms 205240 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 197196 KB Output is correct
2 Correct 77 ms 197184 KB Output is correct
3 Correct 92 ms 197184 KB Output is correct
4 Correct 88 ms 197196 KB Output is correct
5 Correct 105 ms 197128 KB Output is correct
6 Correct 133 ms 198736 KB Output is correct
7 Correct 242 ms 200456 KB Output is correct
8 Correct 286 ms 202592 KB Output is correct
9 Correct 1252 ms 205240 KB Output is correct
10 Correct 85 ms 197164 KB Output is correct
11 Correct 78 ms 197092 KB Output is correct
12 Correct 90 ms 197192 KB Output is correct
13 Correct 86 ms 197176 KB Output is correct
14 Correct 96 ms 197232 KB Output is correct
15 Correct 129 ms 198804 KB Output is correct
16 Correct 237 ms 200416 KB Output is correct
17 Correct 285 ms 202544 KB Output is correct
18 Correct 1236 ms 205236 KB Output is correct
19 Execution timed out 1592 ms 251596 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 197196 KB Output is correct
2 Correct 77 ms 197184 KB Output is correct
3 Correct 92 ms 197184 KB Output is correct
4 Correct 88 ms 197196 KB Output is correct
5 Correct 105 ms 197128 KB Output is correct
6 Correct 133 ms 198736 KB Output is correct
7 Correct 242 ms 200456 KB Output is correct
8 Correct 286 ms 202592 KB Output is correct
9 Correct 1252 ms 205240 KB Output is correct
10 Correct 76 ms 197200 KB Output is correct
11 Correct 94 ms 197200 KB Output is correct
12 Correct 99 ms 197204 KB Output is correct
13 Correct 85 ms 197184 KB Output is correct
14 Correct 94 ms 197152 KB Output is correct
15 Correct 138 ms 198808 KB Output is correct
16 Correct 254 ms 200456 KB Output is correct
17 Correct 279 ms 202516 KB Output is correct
18 Correct 1203 ms 205236 KB Output is correct
19 Runtime error 254 ms 399704 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 257 ms 399812 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 80 ms 197144 KB Output is correct
2 Runtime error 267 ms 399832 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -