Submission #944794

#	Time	Username	Problem	Language	Result	Execution time	Memory
944794		phoenix0423	Passport (JOI23_passport)	C++17	100 / 100	743 ms	128780 KiB

passport

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int INF = 1e9 + 7;
int l[maxn], r[maxn], ans[maxn];
int d0[maxn], d1[maxn];
vector<pll> adj[maxn * 4];
int idx[maxn];
int n;

void build(int v = 1, int l = 0, int r = n - 1){
    if(l == r){
        idx[l] = v;
        return;
    }
    int m = (l + r) / 2;
    adj[v * 2].eb(v, 0);
    adj[v * 2 + 1].eb(v, 0);
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
}

void add(int id, int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        if(idx[id] != v) adj[v].eb(idx[id], 1);
        return;
    }
    int m = (L + R) / 2;
    add(id, l, r, v * 2, L, m);
    add(id, l, r, v * 2 + 1, m + 1, R);
}

vector<int> dijkstra(int st){
    vector<int> dist(n * 4, INF);
    dist[st] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({0, st});
    while(!q.empty()){
        auto [d, pos] = q.top(); q.pop();
        if(dist[pos] != d) continue;
        for(auto [x, w] : adj[pos]){
            if(dist[x] > dist[pos] + w){
                dist[x] = dist[pos] + w;
                q.push({dist[x], x});
            }
        }
    }
    dist[st] = 1;
    return dist;
}

signed main(void){
    fastio;
    cin>>n; 
    build();
    for(int i = 0; i < n; i++){
        cin>>l[i]>>r[i];
        l[i] --, r[i] --;
        add(i, l[i], r[i]);
    }
    auto dist = dijkstra(idx[0]), d1 = dijkstra(idx[n - 1]);
    for(int i = 0; i < n * 4; i++){
        dist[i] += d1[i];
    }
    for(int i = 0; i < n; i++) dist[idx[i]] --;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    for(int i = 0; i < n; i++) q.push({dist[idx[i]], idx[i]});
    while(!q.empty()){
        auto [d, pos] = q.top(); q.pop();
        if(dist[pos] != d) continue;
        for(auto [x, w] : adj[pos]){
            if(dist[x] > dist[pos] + w){
                dist[x] = dist[pos] + w;
                q.push({dist[x], x});
            }
        }
    }
    int Q;
    cin>>Q;
    for(int i = 0; i < Q; i++){
        int x;
        cin>>x;
        x = idx[x - 1];
        cout<<(dist[x] <= n ? dist[x] : -1)<<"\n";
    }
}

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