oj.uz

Submission #721804

# Submission time Handle Problem Language Result Execution time Memory
721804 2023-04-11T07:27:56 Z Mr_Husanboy Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 226244 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
    return a.size();
}
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
#define ff first
#define ss second

void solve(){
    int n, q; cin >> n >> q;
    vector<pair<int,int>> e(n);
   // map<int,int> mp;
    for(int i = 0; i < n; i ++){
        cin >> e[i].ff >> e[i].ss; 
        //mp[e[i].ff] = 1; mp[e[i].ss] = 1;
    }
    vector<vector<int>> g(n);
    for(int i = 0; i < n; i ++){
        for(int j = 0;j < n; j ++){
            if(i == j) continue;
            if(e[i].ss >= e[j].ff && e[i].ss <= e[j].ss){
                //cout << i + 1 << ' ' << j + 1 << endl;
                g[i].push_back(j);
            }
        }
    }
    vector dis(n, vector(n, 1e9));
    auto bfs = [&](int i)->void{
        queue<int> q;
        vector<int> used(n);
        q.push(i);
        dis[i][i] = 0;
        used[i] = 1;
        while(!q.empty()){
            int t = q.front();
            q.pop();
            for(auto u : g[t]){
                if(used[u]) continue;
                used[u] = 1;
                dis[i][u] = dis[i][t] + 1;
                q.push(u);
            }
        }
    };
    vector<int> done(n);
    while(q --){
        int a, b; cin >> a >> b;
        a --; b --;
        if(!done[a]) bfs(a);
        if(dis[a][b] == inf){
            cout << "impossible\n";
        }else cout << dis[a][b] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcases = 1;
    //cin >> testcases;
    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else cout << '\n';
        cout << "__________________" << endl;
        #endif
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1559 ms 3632 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 8148 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 16 ms 8916 KB Output is correct
7 Correct 25 ms 9732 KB Output is correct
8 Correct 26 ms 10836 KB Output is correct
9 Correct 106 ms 12244 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 8148 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 16 ms 8916 KB Output is correct
7 Correct 25 ms 9732 KB Output is correct
8 Correct 26 ms 10836 KB Output is correct
9 Correct 106 ms 12244 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 10 ms 8204 KB Output is correct
13 Correct 10 ms 8148 KB Output is correct
14 Correct 10 ms 8148 KB Output is correct
15 Correct 16 ms 9008 KB Output is correct
16 Correct 26 ms 9764 KB Output is correct
17 Correct 29 ms 10836 KB Output is correct
18 Correct 105 ms 12244 KB Output is correct
19 Execution timed out 1585 ms 226244 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 12 ms 8148 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 16 ms 8916 KB Output is correct
7 Correct 25 ms 9732 KB Output is correct
8 Correct 26 ms 10836 KB Output is correct
9 Correct 106 ms 12244 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 12 ms 8148 KB Output is correct
13 Correct 9 ms 8148 KB Output is correct
14 Correct 12 ms 8188 KB Output is correct
15 Correct 20 ms 8916 KB Output is correct
16 Correct 35 ms 9732 KB Output is correct
17 Correct 25 ms 10836 KB Output is correct
18 Correct 117 ms 12244 KB Output is correct
19 Execution timed out 1577 ms 3716 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 1560 ms 3648 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 1559 ms 3632 KB Time limit exceeded
3 Halted 0 ms 0 KB -