Submission #805193

#	Time	Username	Problem	Language	Result	Execution time	Memory
805193		thimote75	Passport (JOI23_passport)	C++14	48 / 100	2094 ms	923852 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;

    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(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:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < todo_list.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~

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