oj.uz

Submission #580864

# Submission time Handle Problem Language Result Execution time Memory
580864 2022-06-22T03:21:14 Z talant117408 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 42624 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;
    queue <int> K;
    K.push(p);
    
    while (!K.empty()) {
        auto v = K.front(); K.pop();
        for (auto to : graph[v]) {
            if (shortest[p][to] > shortest[p][v] + 1) {
                shortest[p][to] = shortest[p][v] + 1;
                K.push(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 33 ms 4196 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 18 ms 10540 KB Output is correct
4 Correct 16 ms 10652 KB Output is correct
5 Correct 22 ms 10536 KB Output is correct
6 Correct 49 ms 11340 KB Output is correct
7 Correct 141 ms 12108 KB Output is correct
8 Correct 173 ms 13292 KB Output is correct
9 Correct 893 ms 14620 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 18 ms 10540 KB Output is correct
4 Correct 16 ms 10652 KB Output is correct
5 Correct 22 ms 10536 KB Output is correct
6 Correct 49 ms 11340 KB Output is correct
7 Correct 141 ms 12108 KB Output is correct
8 Correct 173 ms 13292 KB Output is correct
9 Correct 893 ms 14620 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 17 ms 10580 KB Output is correct
13 Correct 15 ms 10580 KB Output is correct
14 Correct 22 ms 10580 KB Output is correct
15 Correct 62 ms 11336 KB Output is correct
16 Correct 146 ms 12168 KB Output is correct
17 Correct 170 ms 13256 KB Output is correct
18 Correct 938 ms 14620 KB Output is correct
19 Execution timed out 1599 ms 42624 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 18 ms 10540 KB Output is correct
4 Correct 16 ms 10652 KB Output is correct
5 Correct 22 ms 10536 KB Output is correct
6 Correct 49 ms 11340 KB Output is correct
7 Correct 141 ms 12108 KB Output is correct
8 Correct 173 ms 13292 KB Output is correct
9 Correct 893 ms 14620 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 17 ms 10632 KB Output is correct
13 Correct 14 ms 10580 KB Output is correct
14 Correct 20 ms 10564 KB Output is correct
15 Correct 51 ms 11340 KB Output is correct
16 Correct 147 ms 12136 KB Output is correct
17 Correct 213 ms 13240 KB Output is correct
18 Correct 904 ms 14556 KB Output is correct
19 Incorrect 27 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 33 ms 4196 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 33 ms 4196 KB Output isn't correct
3 Halted 0 ms 0 KB -