Submission #1184558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184558		Gray	Passport (JOI23_passport)	C++20	48 / 100	2098 ms	274356 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]);
    }
    // for (ll i=1; i<(4*(n+1)); i++){
    //     cout << i << " - " << bid[i] << ": ";
    //     for (auto [v, w]:rA[i]) cout << v << "-" << bid[v] << "  ";
    //     cout << ln;
    // }
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    que.push({0, ids[1]});
    vector<ll> dist1(4*(n+1), 2e9);
    while (!que.empty()){
        ll u, w; tie(w, u)=que.top(); que.pop();
        if (dist1[u]<2e9) continue;
        dist1[u]=w;
        for (auto [v, c]:rA[u]){
            if (dist1[v]==2e9) que.push({c+w, v});
        }
    }
    // for (ll i=1; i<=n; i++){
    //     cout << dist1[ids[i]] << " ";
    // }
    // cout << ln;
    que.push({0, ids[n]});
    vector<ll> distn(4*(n+1), 2e9);
    while (!que.empty()){
        ll u, w; tie(w, u)=que.top(); que.pop();
        if (distn[u]<2e9) continue;
        distn[u]=w;
        for (auto [v, c]:rA[u]){
            if (distn[v]==2e9) que.push({c+w, v});
        }
    }
    // for (ll i=1; i<=n; i++){
    //     cout << distn[ids[i]] << " ";
    // }
    // cout << ln;

    vector<ll> distF(4*(n+1), INF);
    for (ll i=1; i<=n; i++){

        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]<INF) continue;
        // cout << u << "~" << bid[u] << " <-> " << w << ": ";
        distF[u]=w;
        for (auto [v, c]:rA[u]){
            // cout << v << "&" << c << "  ";
            if (distF[v]==INF) 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: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46