oj.uz

Submission #580863

# Submission time Handle Problem Language Result Execution time Memory
580863 2022-06-22T03:19:43 Z talant117408 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 41196 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];

void bfs(int p) {
    for (int i = 1; i < 5003; 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 n, 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 2772 KB Output is correct
2 Incorrect 38 ms 4416 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 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 25 ms 22300 KB Output is correct
4 Correct 20 ms 22292 KB Output is correct
5 Correct 28 ms 22220 KB Output is correct
6 Correct 64 ms 23004 KB Output is correct
7 Correct 188 ms 23752 KB Output is correct
8 Correct 223 ms 24824 KB Output is correct
9 Correct 1085 ms 26180 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 25 ms 22300 KB Output is correct
4 Correct 20 ms 22292 KB Output is correct
5 Correct 28 ms 22220 KB Output is correct
6 Correct 64 ms 23004 KB Output is correct
7 Correct 188 ms 23752 KB Output is correct
8 Correct 223 ms 24824 KB Output is correct
9 Correct 1085 ms 26180 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct
11 Correct 1 ms 2772 KB Output is correct
12 Correct 23 ms 22228 KB Output is correct
13 Correct 20 ms 22292 KB Output is correct
14 Correct 28 ms 22228 KB Output is correct
15 Correct 68 ms 23056 KB Output is correct
16 Correct 166 ms 23880 KB Output is correct
17 Correct 201 ms 25036 KB Output is correct
18 Correct 1128 ms 26460 KB Output is correct
19 Execution timed out 1550 ms 41196 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 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 25 ms 22300 KB Output is correct
4 Correct 20 ms 22292 KB Output is correct
5 Correct 28 ms 22220 KB Output is correct
6 Correct 64 ms 23004 KB Output is correct
7 Correct 188 ms 23752 KB Output is correct
8 Correct 223 ms 24824 KB Output is correct
9 Correct 1085 ms 26180 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 25 ms 22268 KB Output is correct
13 Correct 20 ms 22228 KB Output is correct
14 Correct 26 ms 22292 KB Output is correct
15 Correct 63 ms 23044 KB Output is correct
16 Correct 180 ms 23884 KB Output is correct
17 Correct 203 ms 24936 KB Output is correct
18 Correct 1051 ms 26256 KB Output is correct
19 Incorrect 22 ms 3496 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 4264 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 2772 KB Output is correct
2 Incorrect 38 ms 4416 KB Output isn't correct
3 Halted 0 ms 0 KB -