Submission #805195

#	Time	Username	Problem	Language	Result	Execution time	Memory
805195		thimote75	Passport (JOI23_passport)	C++14	100 / 100	691 ms	87308 KiB

passport

#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, height, start;

    VSegTree (int _size) {
        size   = _size;
        height = ceil(log2(size));
        start  = 1 << height;

        tree   .resize(start << 1);
        visited.resize(size);
    }

    void insert (int node, int l, int r) {
        l += start; r += start;

        while (l < r) {
            if ((l & 1) == 1) tree[l].push_back(node);
            if ((r & 1) == 0) tree[r].push_back(node);

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) tree[l].push_back(node);
    }
    idata query (int node) {
        idata answer;

        node += start;
        while (node != 0) {
            for (int u : tree[node]) if (!visited[u]) {
                visited[u] = true;
                answer.push_back(u);
            }
            
            tree[node].clear();

            node >>= 1;
        }

        return answer;
    }
};

int N;
idata bfs (vd &start, VSegTree tree) {
    igrid todo_list(2 * N + 3);
    for (const auto &st : start) {
        //cout << st.first << " = dist(" << st.second << ")\n";

        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);
        //cout << l << " " << r << ": " << (l == 0) << " " << (r == N - 1) << endl;
        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);
    //for (int u : dp_left) cout << u << " "; cout << endl;
    //for (int u : dp_right) cout << u << " "; cout << endl;

    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 (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46