oj.uz

Submission #805171

# Submission time Handle Problem Language Result Execution time Memory
805171 2023-08-03T13:40:22 Z thimote75 Passport (JOI23_passport) C++14
0 / 100
 2000 ms 846044 KB 
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using bdata = vector<bool>;

using di = pair<int, int>;
using vd = vector<di>;

struct VSegTree {
    igrid tree;
    bdata visited;
    int size;

    VSegTree (int _size) {
        size   = _size;

        tree   .resize(size);
        visited.resize(size);
    }

    void insert (int node, int left, int right) {
        for (int i = left; i <= right; i ++)
            tree[i].push_back(node);
        visited[node] = false;
    }
    idata query (int node) {
        idata answer;
        for (int u : tree[node]) if (!visited[u]) {
            visited[u] = true;
            answer.push_back(u);
        }

        tree[node].clear();
        return answer;
    }
};

int N;
idata bfs (vd start, VSegTree tree) {
    igrid todo_list(N + 3);
    for (const auto &st : start)
        todo_list[st.first].push_back(st.second);
    
    idata answer (N, -1);
    for (int i = 0; i < todo_list.size(); i ++) {
        for (int curr : todo_list[i]) {
            if (answer[curr] != -1) continue ;
            answer[curr] = i;

            for (int next : tree.query(curr))
                todo_list[i + 1].push_back(next);
        }
    }
    
    return answer;
}

int main () {
    cin >> N;

    VSegTree tree(N);

    vd  left_start;
    vd right_start;

    for (int i = 0; i < N; i ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        tree.insert(i, l, r);
        if (l == 0    )  left_start.push_back({ 0, i });
        if (r == N - 1) right_start.push_back({ 0, i });
    }

    idata dp_left  = bfs( left_start, tree);
    idata dp_right = bfs(right_start, tree);

    vd final_start;
    for (int i = 0; i < N; i ++) {
        if (dp_left[i] == -1 || dp_right[i] == -1) continue;

        final_start.push_back({ dp_left[i] + dp_right[i] + 1, i });
    }

    idata dp_answer = bfs(final_start, tree);

    int Q; cin >> Q;
    for (int q = 0; q < Q; q ++) {
        int x; cin >> x;
        x --;

        cout << dp_answer[x] << "\n";
    }
}

Compilation message

passport.cpp: In function 'idata bfs(vd, VSegTree)':
passport.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < todo_list.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.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 1 ms 212 KB Output is correct
4 Execution timed out 2101 ms 846044 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Runtime error 2 ms 724 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Runtime error 2 ms 724 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Runtime error 2 ms 724 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #5
0 / 46.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 1 ms 212 KB Output is correct
4 Execution timed out 2101 ms 846044 KB Time limit exceeded
5 Halted 0 ms 0 KB -