Submission #1109863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109863		Zero_OP	Passport (JOI23_passport)	C++14	100 / 100	543 ms	89780 KiB

passport

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;

    vector<vector<pair<int, int>>> adj(N * 4);
    vector<int> ln(N * 4), rn(N * 4);

    int n = N;
    function<int(int, int)> build = [&](int l, int r){
        if(l == r) return l;
        int mid = l + r >> 1;

        int o = n++, lc = build(l, mid), rc = build(mid + 1, r);
        ln[o] = lc;
        rn[o] = rc;
        adj[lc].emplace_back(o, 0);
        adj[rc].emplace_back(o, 0);
        return o;
    };

    function<void(int, int, int, int, int, int)> addEdge = [&](
        int cur, int l, int r, int u, int v, int s){
        if(u <= l && r <= v){
            adj[cur].emplace_back(s, 1);
        } else{
            int mid = l + r >> 1;
            if(u <= mid) addEdge(ln[cur], l, mid, u, v, s);
            if(mid < v) addEdge(rn[cur], mid + 1, r, u, v, s);
        }
    };

    int rt = build(0, N - 1);
    for(int i = 0; i < N; ++i){
        int l, r;
        cin >> l >> r;
        --l, --r;
        addEdge(rt, 0, N - 1, l, r, i);
    }

    auto bfs_deque = [&](int s, vector<vector<pair<int, int>>>& adj) -> vector<int>{
        vector<int> dist(4 * N, -1);
        dist[s] = 0;
        deque<int> dq;

        dq.push_back(s);
        while(!dq.empty()){
            int u = dq.front(); dq.pop_front();

            for(auto [v, w] : adj[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u] + w;
                    if(w == 0) dq.push_front(v);
                    else dq.push_back(v);
                }
            }
        }

        return dist;
    };

    vector<int> distS = bfs_deque(0, adj), distT = bfs_deque(N - 1, adj);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    vector<int> answer(N * 4, -1);
    for(int i = 0; i < N; ++i){
        if(distS[i] != -1 && distT[i] != -1){
            answer[i] = max(1, distS[i]) + max(1, distT[i]) - 1;
            pq.push(make_pair(answer[i], i));
        }
    }

    while(!pq.empty()){
        int cur, u;
        tie(cur, u) = pq.top(); pq.pop();

        for(auto [v, w] : adj[u]){
            if(answer[v] == -1 || answer[v] > answer[u] + w){
                answer[v] = answer[u] + w;
                pq.push(make_pair(answer[v], v));
            }
        }
    }

    int Q;
    cin >> Q;
    while(Q--){
        int u;
        cin >> u;
        --u;
        cout << answer[u] << '\n';
    }

    return 0;
}

Compilation message (stderr)

passport.cpp: In lambda function:
passport.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = l + r >> 1;
      |                   ~~^~~
passport.cpp: In lambda function:
passport.cpp:37:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |             int mid = l + r >> 1;
      |                       ~~^~~
passport.cpp: In lambda function:
passport.cpp:60:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |             for(auto [v, w] : adj[u]){
      |                      ^
passport.cpp: In function 'int main()':
passport.cpp:87:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for(auto [v, w] : adj[u]){
      |                  ^

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