Submission #928721

#	Time	Username	Problem	Language	Result	Execution time	Memory
928721		Darren0724	Passport (JOI23_passport)	C++17	100 / 100	874 ms	124152 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int M=N*5;
const int INF=1e8;
int n;
vector dis(3,vector(M,INF));
vector<pair<int,int>> adj[M],adj1[M];
vector<int> rec(N);
void link(int a,int b,int c){
    adj[b].push_back({a,c});
}
void build(int id=1,int l=1,int r=n+1){
    if(r-l==1)return link(n+id,l,1);
    int m=(l+r)>>1;
    link(n+id,n+id*2,0);
    link(n+id,n+id*2+1,0);
    build(id<<1,l,m);
    build(id<<1|1,m,r);
}
void connect(int id,int l,int r,int a,int b,int x){
    if(a<=l&&b>=r)return link(x,n+id,0);
    if(r-l==1)return;
    int m=(l+r)>>1;
    if(a<m)connect(id<<1,l,m,a,b,x);
    if(b>m)connect(id<<1|1,m,r,a,b,x);
}
void dijk(vector<int> &dis){
    priority_queue<pair<int,int>> pq;
    for(int i=1;i<=n;i++){
        pq.push({-dis[i],i});
    }
    while(pq.size()){
        auto [a,b]=pq.top();
        pq.pop();
        a=-a;
        if(dis[b]!=a)continue;
        for(auto [c,d]:adj[b]){
            int cost=dis[b]+d;
            if(cost<dis[c]){
                dis[c]=cost;
                pq.push({-cost,c});
            }
        }
    }
}
int32_t main() {
    LCBorz;
    cin>>n;
    build();
    vector<int> b(N),c(N);
    for(int i=1;i<=n;i++){
        cin>>b[i]>>c[i];
        connect(1,1,n+1,b[i],c[i]+1,i);
    }
    dis[0][1]=dis[1][n]=0;
    dijk(dis[0]);
    dijk(dis[1]);
    for(int i=1;i<=n;i++){
        dis[2][i]=dis[0][i]+dis[1][i]-(1<i&&i<n);
    }
    dijk(dis[2]);
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int p;cin>>p;
        cout<<(dis[2][p]>=INF?-1:dis[2][p])<<endl;
    }

    return 0;
}

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