Submission #1097415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097415		vjudge1	Passport (JOI23_passport)	C++17	100 / 100	999 ms	121756 KiB

passport

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9+69;
const int MAXN = 2e5+3;

int nArr, q, x;
int numNode;

vector<pair<int,int>> e[6*MAXN];

int ans;
int f[6*MAXN];
int ID[6*MAXN];
bool vis[6*MAXN];

void STbuild(int idx=1, int l=1, int r=nArr){
    if(l==r){
        e[l].emplace_back(ID[idx], 0);
        return;
    }
    int mid = l+r>>1;
    e[ID[idx<<1]].emplace_back(ID[idx], 0);
    e[ID[idx<<1|1]].emplace_back(ID[idx], 0);
    STbuild(idx<<1, l, mid);
    STbuild(idx<<1|1, mid+1, r);
}

void STunion(int z, int u, int v, int idx=1, int l=1, int r=nArr){
    if(v<l || r<u)return;
    if(u<=l && r<=v){
        e[ID[idx]].push_back({z, 0});
        return;
    }
    int mid = l+r>>1;
    STunion(z,u,v,idx<<1,l,mid);
    STunion(z,u,v,idx<<1|1,mid+1,r);
}

int S[2][6*MAXN];

void dijsktra(int x, int f[]){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    pq.emplace(0, x);
    for(int i=1; i<=numNode; ++i) f[i] = INF;
    f[x] = 0;

    while(!pq.empty()){
        pair<int,int> z = pq.top(); pq.pop();
        int du = z.first,
            u = z.second;
        if(du>f[u])continue;
        for(pair<int,int> &z : e[u]){
            int v = z.first,
                w = z.second;
            if(f[u]+w < f[v]){
                f[v] = f[u]+w;
                pq.emplace(f[v], v);
            }
        }
        cout << '\n';
    }
}


signed main()
{   
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> nArr;
    numNode = nArr;
    for(int i=1; i<=4*nArr; ++i) ID[i] = ++numNode;
    STbuild();
    for(int l, r, i=1; i<=nArr; ++i){
        cin >> l >> r;
        STunion(++numNode, l, r); 
        e[numNode].emplace_back(i, 1);
    }
    dijsktra(1, S[0]);
    dijsktra(nArr, S[1]);

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for(int i=1; i<=numNode; ++i){
        f[i] = S[0][i] + S[1][i];
        pq.emplace(f[i], i);
    }

    // for(int i=1; i<=numNode; ++i) cout << S[0][i] << ' '; cout << '\n';
    // for(int i=1; i<=numNode; ++i) cout << S[1][i] << ' '; cout << '\n';
    // for(int i=1; i<=numNode; ++i) cout << f[i] << ' '; cout << '\n';

    while(!pq.empty()){
        pair<int,int> z = pq.top(); pq.pop();
        int du = z.first,
            u = z.second;
        if(du>f[u])continue;
        // cout << u << '\n';
        for(pair<int,int> &z : e[u]){
            int v = z.first,
                w = z.second;
            if(f[u]+w < f[v]){
                f[v] = f[u]+w;
                pq.emplace(f[v], v);
            }
        }
    }
    // for(int i=1; i<=numNode; ++i) cout << f[i] << ' '; cout << '\n';
    
    cin >> q;
    while(q--){
        cin >> x;
        cout << (f[x]>=INF ? -1 : f[x]) << '\n';
    } 

    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void STbuild(int, int, int)':
passport.cpp:26:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l+r>>1;
      |               ~^~
passport.cpp: In function 'void STunion(int, int, int, int, int, int)':
passport.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l+r>>1;
      |               ~^~

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