Submission #1306493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306493		mohammadsam	Passport (JOI23_passport)	C++20	22 / 100	537 ms	118024 KiB

passport

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           (u<<1)
#define rid           ((lid)|1)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 1e17 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n,q;
int L[N],R[N];
int dis[2][N<<2];
int val[N<<2];
int id[N];
int num = 0;
vector<pii> g[N<<2];
void build(int u=1,int l=1,int r=n+1){
    num = max(num,u);
    if(r-l==1){
        id[l] = u;
        return;
    }
    int mid = (l+r)>>1;
    build(lid,l,mid);
    build(rid,mid,r);
    // cout << lid << " -> " << u << " " << 0 << endl;
    // cout << rid << " -> " << u << " " << 0 << endl;
    g[lid].pb({u,0});
    g[rid].pb({u,0});
}
void Add(int s,int e,int x,int u=1,int l=1,int r=n+1){
    if(e <= s || e <= l || r <= s) return;
    if(s <= l && r <= e){
        g[u].pb({id[x],1});
        // cout << u << " -> " << id[x] << sep << 1 << endl;
        return;
    }
    int mid = (l+r)>>1;
    Add(s,e,x,lid,l,mid);
    Add(s,e,x,rid,mid,r);
}
deque<int> Q;
void bfs(int j){
    fill(dis[j],dis[j] + num + 2,inf);
    for(auto h : Q) dis[j][h] =0;
    while(!Q.empty()){
        int u = Q.front();Q.pop_front();
        for(auto h : g[u]){
            if(h.sec == 0){
                if(dis[j][h.fi] > dis[j][u]){
                    Q.push_front(h.fi);
                    dis[j][h.fi] = dis[j][u];
                }
            }
            else {
                if(dis[j][h.fi] > dis[j][u] + 1){
                    Q.pb(h.fi);
                    dis[j][h.fi] = dis[j][u] + 1;
                }
            }
        }
    }
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
void dijk(){
    for(int i =1 ;i <= num ;i++) pq.push({val[i],i});
    while(!pq.empty()){
        auto [d,u] = pq.top();pq.pop();
        if(d != val[u]) continue;
        for(auto h : g[u]){
            if(val[h.fi] > val[u] + h.sec){
                val[h.fi] = val[u] + h.sec;
                pq.push({val[h.fi],h.fi});
            }
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n ;
    for(int i = 1;i <= n;i++) cin >> L[i] >> R[i];
    build();
    for(int i =1 ;i <= n;i++){
        Add(L[i],R[i]+1,i);
    }
    Q.pb(id[n]);
    bfs(0);
    Q.pb(id[1]);
    bfs(1); 
    for(int i =1 ;i <= num;i++) {
        if(dis[0][i] && dis[1][i]) val[i] = dis[0][i] + dis[1][i] - 1;
        else val[i] = inf;
    }
    dijk();
    cin >> q;
    for(int i =1 ;i <= q;i++){
        int x;
        cin >> x;
        int ans = val[id[x]];
        ans = min(ans,dis[0][id[x]] + dis[1][id[n]]);
        ans = min(ans,dis[1][id[x]] + dis[0][id[1]]);
        if(ans > n+1) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

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