Submission #1184580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184580		Gray	Passport (JOI23_passport)	C++20	100 / 100	876 ms	239780 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

void set_id(ll tl, ll tr, ll v, vector<ll> &id, vector<vector<pair<ll, ll>>> &adj, vector<vector<pair<ll, ll>>> &radj, vector<ll> &bid){
    if (tl==tr){
        id[tl]=v; bid[v]=tl;
    }else{
        ll tm = (tl+tr)/2;
        adj[v].push_back({v*2, 0}); adj[v].push_back({v*2+1, 0});
        radj[v*2].push_back({v, 0}); radj[v*2+1].push_back({v, 0});
        set_id(tl, tm, v*2, id, adj, radj, bid);
        set_id(tm+1, tr, v*2+1, id, adj, radj, bid);
    }
}

void assign(ll tl, ll tr, ll v, ll l, ll r, vector<vector<pair<ll, ll>>> &adj, vector<vector<pair<ll, ll>>> &radj, ll cid){
    if (tl==l and tr==r){
        if (v!=cid) {
            adj[cid].push_back({v, 1});
            radj[v].push_back({cid, 1});
        }
    }else if (l>r) return;
    else{
        ll tm = (tl+tr)/2;
        assign(tl, tm, v*2, l, min(r, tm), adj, radj, cid);
        assign(tm+1, tr, v*2+1, max(l, tm+1), r, adj, radj, cid);
    }
}

void solve(){
    ll n; cin >> n;
    vector<vector<pair<ll, ll>>> A(4*(n+1)), rA(4*(n+1));
    vector<ll> ids(n+1), bid(4*(n+1), -1);
    set_id(1, n, 1, ids, A, rA, bid);
    for (ll i=1; i<=n; i++){
        ll l, r; cin >> l >> r;
        assign(1, n, 1, l, r, A, rA, ids[i]);
    }
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    vector<ll> dist1(4*(n+1), 2e9);
    que.push({0, ids[1]});
    dist1[ids[1]]=0;
    while (!que.empty()){
        ll u, w; tie(w, u)=que.top(); que.pop();
        if (dist1[u]<w) continue;
        dist1[u]=w;
        for (auto [v, c]:rA[u]){
            if (dist1[v]>c+w) {
                dist1[v]=c+w; que.push({c+w, v});
            }
        }
    }
    vector<ll> distn(4*(n+1), 2e9);
    que.push({0, ids[n]}); distn[ids[n]]=0;
    while (!que.empty()){
        ll u, w; tie(w, u)=que.top(); que.pop();
        if (distn[u]<w) continue;
        for (auto [v, c]:rA[u]){
            if (distn[v]>c+w) {
                distn[v]=c+w; que.push({c+w, v});
            }
        }
    }
    vector<ll> distF(4*(n+1), INF);
    for (ll i=1; i<=n; i++){
        distF[ids[i]]=dist1[ids[i]]+distn[ids[i]]-1+((i==1 or i==n));
        que.push({dist1[ids[i]]+distn[ids[i]]-1+((i==1 or i==n)), ids[i]});
        // cout << dist1[ids[i]]+distn[ids[i]]-1+((i==1 or i==n)) << " - ";
    }
    // cout << ln;
    while (!que.empty()){
        ll u, w; tie(w, u)=que.top(); que.pop();
        if (distF[u]<w) continue;
        for (auto [v, c]:rA[u]){
            if (distF[v]>c+w) {
                distF[v]=c+w; que.push({c+w, v});
            }
        }
        // cout << ln;
    }
    // for (ll i=1; i<=n; i++) cout << distF[ids[i]] << " ";
    // cout << ln;
    ll q; cin >> q;
    while (q--){
        ll i; cin >> i;
        cout << (distF[ids[i]]>=2e9?-1:distF[ids[i]]) << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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