oj.uz

Submission #697800

# Submission time Handle Problem Language Result Execution time Memory
697800 2023-02-11T06:12:49 Z Duy_e Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 51876 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 1e5 + 5;

ll n, q, s[N], e[N];
vector <int> cmp, out[2 * N], in[2 * N];
vector <int> d[N];

const ll Nmax = 5005;
int dist[Nmax][Nmax];
void bfs(int st, int *f) {
    rep(i, 1, n) f[i] = 1e9;
    f[st] = 0;
    queue <int> q;
    q.push(st);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int v: d[u]) if (f[v] > f[u] + 1) {
            f[v] = f[u] + 1;
            q.push(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    rep(i, 1, n) {
        cin >> s[i] >> e[i];
        cmp.push_back(s[i]);
        cmp.push_back(e[i]);
    }

    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

    auto find = [&] (ll x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
    };

    rep(i, 1, n) {
        s[i] = find(s[i]);
        e[i] = find(e[i]);
        in[s[i]].push_back(i);
        out[e[i]].push_back(i);
    }

    set <int> save;
    rep(timer, 1, 2 * n) {
        for (int i: in[timer]) save.insert(i);
        for (int i: out[timer]) {
            for (int j: save)
                d[i].push_back(j);
        }

        for (int i: out[timer])
            save.erase(i);
    }

    rep(i, 1, n) bfs(i, dist[i]);

    while (q --) {
        int u, v;
        cin >> u >> v;
        if (dist[u][v] >= (int)1e9)
            cout << "impossible\n";
        else
            cout << dist[u][v] << '\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Execution timed out 1576 ms 42588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 18 ms 20104 KB Output is correct
4 Correct 18 ms 20060 KB Output is correct
5 Correct 19 ms 20132 KB Output is correct
6 Correct 58 ms 21020 KB Output is correct
7 Correct 142 ms 21764 KB Output is correct
8 Correct 175 ms 22716 KB Output is correct
9 Correct 895 ms 24164 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 18 ms 20104 KB Output is correct
4 Correct 18 ms 20060 KB Output is correct
5 Correct 19 ms 20132 KB Output is correct
6 Correct 58 ms 21020 KB Output is correct
7 Correct 142 ms 21764 KB Output is correct
8 Correct 175 ms 22716 KB Output is correct
9 Correct 895 ms 24164 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 8 ms 12112 KB Output is correct
12 Correct 21 ms 20104 KB Output is correct
13 Correct 14 ms 20068 KB Output is correct
14 Correct 21 ms 20052 KB Output is correct
15 Correct 52 ms 20856 KB Output is correct
16 Correct 143 ms 21680 KB Output is correct
17 Correct 175 ms 22748 KB Output is correct
18 Correct 903 ms 24080 KB Output is correct
19 Execution timed out 1552 ms 51876 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 18 ms 20104 KB Output is correct
4 Correct 18 ms 20060 KB Output is correct
5 Correct 19 ms 20132 KB Output is correct
6 Correct 58 ms 21020 KB Output is correct
7 Correct 142 ms 21764 KB Output is correct
8 Correct 175 ms 22716 KB Output is correct
9 Correct 895 ms 24164 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Correct 18 ms 20144 KB Output is correct
13 Correct 14 ms 20056 KB Output is correct
14 Correct 19 ms 20012 KB Output is correct
15 Correct 54 ms 20776 KB Output is correct
16 Correct 155 ms 21712 KB Output is correct
17 Correct 180 ms 22756 KB Output is correct
18 Correct 930 ms 24064 KB Output is correct
19 Execution timed out 1562 ms 43400 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 1594 ms 43536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Execution timed out 1576 ms 42588 KB Time limit exceeded
3 Halted 0 ms 0 KB -