oj.uz

Submission #580866

# Submission time Handle Problem Language Result Execution time Memory
580866 2022-06-22T03:23:53 Z talant117408 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 42192 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e5+7;
vector <int> graph[N];
int shortest[5003][5003];
int s[N], e[N], n;

void bfs(int p) {
    for (int i = 1; i <= n; i++) {
        shortest[p][i] = 2e9;
    }
    shortest[p][p] = 0;
    priority_queue <pii> K;
    K.push(mp(0, p));
    
    while (!K.empty()) {
        auto v = K.top().second; K.pop();
        for (auto to : graph[v]) {
            if (shortest[p][to] > shortest[p][v] + 1) {
                shortest[p][to] = shortest[p][v] + 1;
                K.push(mp(-shortest[p][to], to));
            }
        }
    }
}

void solve() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i];
    }
    vector <pii> queries(q);
    for (auto &to : queries) cin >> to.first >> to.second;
    
    if (n <= 5000) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                if (s[j] <= e[i] && e[i] <= e[j]) graph[i].pb(j);
            }
        }
        for (int i = 1; i <= n; i++) bfs(i);
        for (auto to : queries) {
            if (shortest[to.first][to.second] > 1e9) cout << "impossible" << endl;
            else cout << shortest[to.first][to.second] << endl;
        }
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 38 ms 4280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 29 ms 10632 KB Output is correct
4 Correct 17 ms 10564 KB Output is correct
5 Correct 26 ms 10540 KB Output is correct
6 Correct 70 ms 11308 KB Output is correct
7 Correct 176 ms 12240 KB Output is correct
8 Correct 204 ms 13272 KB Output is correct
9 Correct 992 ms 14560 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 29 ms 10632 KB Output is correct
4 Correct 17 ms 10564 KB Output is correct
5 Correct 26 ms 10540 KB Output is correct
6 Correct 70 ms 11308 KB Output is correct
7 Correct 176 ms 12240 KB Output is correct
8 Correct 204 ms 13272 KB Output is correct
9 Correct 992 ms 14560 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 24 ms 10656 KB Output is correct
13 Correct 16 ms 10580 KB Output is correct
14 Correct 24 ms 10604 KB Output is correct
15 Correct 71 ms 11408 KB Output is correct
16 Correct 178 ms 12140 KB Output is correct
17 Correct 218 ms 13284 KB Output is correct
18 Correct 922 ms 14596 KB Output is correct
19 Execution timed out 1600 ms 42192 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 29 ms 10632 KB Output is correct
4 Correct 17 ms 10564 KB Output is correct
5 Correct 26 ms 10540 KB Output is correct
6 Correct 70 ms 11308 KB Output is correct
7 Correct 176 ms 12240 KB Output is correct
8 Correct 204 ms 13272 KB Output is correct
9 Correct 992 ms 14560 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 23 ms 10556 KB Output is correct
13 Correct 18 ms 10652 KB Output is correct
14 Correct 25 ms 10540 KB Output is correct
15 Correct 67 ms 11336 KB Output is correct
16 Correct 179 ms 12188 KB Output is correct
17 Correct 213 ms 13260 KB Output is correct
18 Correct 968 ms 14548 KB Output is correct
19 Incorrect 21 ms 3412 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 4276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 38 ms 4280 KB Output isn't correct
3 Halted 0 ms 0 KB -