oj.uz

Submission #849863

# Submission time Handle Problem Language Result Execution time Memory
849863 2023-09-15T13:22:17 Z Ahmed57 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 34124 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100001];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    vector<pair<int,int>> v;
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        v.push_back({a,b});
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(i!=j){
                if(v[j].first<=v[i].second&&v[i].second<=v[j].second){
                    adj[i].push_back(j);
                }
            }
        }
    }
    vector<pair<int,int>> qu[n];
    for(int i = 0;i<q;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        qu[a].push_back({b,i});
    }
    int ans[q] = {0};
    int cost[n] = {0};
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cost[j] = 1e9;;
        }
        queue<int> q;q.push(i);
        cost[i] = 0;
        while(!q.empty()){
            int x = q.front();q.pop();
            for(auto j:adj[x]){
                if(cost[j]==1e9){
                    cost[j] = cost[x]+1;
                    q.push(j);
                }
            }
        }
        for(auto j:qu[i]){
            ans[j.second] = cost[j.first];
        }
    }
    for(int i = 0;i<q;i++){
        if(ans[i]==1e9)cout<<"impossible\n";
        else cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 9 ms 2648 KB Output is correct
4 Correct 7 ms 2652 KB Output is correct
5 Correct 10 ms 2648 KB Output is correct
6 Correct 37 ms 3416 KB Output is correct
7 Correct 105 ms 4440 KB Output is correct
8 Correct 124 ms 5488 KB Output is correct
9 Correct 681 ms 6836 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 9 ms 2648 KB Output is correct
4 Correct 7 ms 2652 KB Output is correct
5 Correct 10 ms 2648 KB Output is correct
6 Correct 37 ms 3416 KB Output is correct
7 Correct 105 ms 4440 KB Output is correct
8 Correct 124 ms 5488 KB Output is correct
9 Correct 681 ms 6836 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 9 ms 2652 KB Output is correct
13 Correct 7 ms 2648 KB Output is correct
14 Correct 10 ms 2648 KB Output is correct
15 Correct 37 ms 3420 KB Output is correct
16 Correct 105 ms 4440 KB Output is correct
17 Correct 140 ms 5464 KB Output is correct
18 Correct 668 ms 6840 KB Output is correct
19 Execution timed out 1528 ms 34124 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 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 9 ms 2648 KB Output is correct
4 Correct 7 ms 2652 KB Output is correct
5 Correct 10 ms 2648 KB Output is correct
6 Correct 37 ms 3416 KB Output is correct
7 Correct 105 ms 4440 KB Output is correct
8 Correct 124 ms 5488 KB Output is correct
9 Correct 681 ms 6836 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 9 ms 2648 KB Output is correct
13 Correct 7 ms 2648 KB Output is correct
14 Correct 9 ms 2648 KB Output is correct
15 Correct 38 ms 3628 KB Output is correct
16 Correct 105 ms 4444 KB Output is correct
17 Correct 124 ms 5464 KB Output is correct
18 Correct 678 ms 6844 KB Output is correct
19 Execution timed out 1551 ms 3800 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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