Submission #1098656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098656		flyingkite	Passport (JOI23_passport)	C++17	100 / 100	1855 ms	361856 KiB

passport

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 6e5 + 100;
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll block = 350;
vector<ll>adj[5 * N], rev[5 * N];
ll d[5 * N][2];
ll dp[5 * N];
ll n,q;
struct cmp{
    bool operator()(const pll &a, const pll &b){
        return a.S > b.S;
    }
};
void dijk(ll s, ll typ){
    priority_queue<pll, vector<pll>, cmp>q;
    for(int i = 1; i <= 9 * n;i++) d[i][typ] = inf;
    d[s][typ] = 0;
    q.push({s, d[s][typ]});
    while(q.size()){
        ll u = q.top().F, c = q.top().S; q.pop();
        if(c != d[u][typ]) continue;
        for(auto v : rev[u]){
            if(d[u][typ] + (v >= 8 * n + 1) < d[v][typ]){
                d[v][typ] = d[u][typ] + (v >= 8 * n + 1);
                q.push({v, d[v][typ]});
            }
        }
    }
}
void finalize(){
    priority_queue<pll, vector<pll>, cmp>q;
    for(int i = 1; i <= 9 * n;i++) dp[i] = d[i][0] + d[i][1] - (i > 8 * n + 1 && i < 9 * n), q.push({i, dp[i]});
    while(q.size()){
        ll u = q.top().F, c = q.top().S; q.pop();
        if(c != dp[u]) continue;
        for(auto v : rev[u]){
            if(dp[u] + (v >= 8 * n + 1) < dp[v]){
                dp[v] = dp[u] + (v >= 8 * n + 1);
                q.push({v, dp[v]});
            }
        }
    }
}
void build1(ll id, ll l, ll r){
    if(l == r){
        adj[id].pb(8 * n + l);
        adj[8 * n + l].pb(id);
		rev[id].pb(8 * n + l);
    	rev[8 * n + l].pb(id);
        return;
    }
    ll mid = (l + r) / 2;
    build1(2 * id, l, mid); build1(2 * id + 1, mid + 1, r);
    adj[id].pb(2 * id); adj[id].pb(2 * id + 1);
	rev[2 * id].pb(id); rev[2 * id + 1].pb(id);
}
void build2(ll id, ll l, ll r){
    if(l == r) {
        adj[4 * n + id].pb(8 * n + l);
        adj[8 * n + l].pb(4 * n + id);
        rev[8 * n + l].pb(4 * n + id);
        rev[4 * n + id].pb(8 * n + l);
        return;
    }
    ll mid = (l + r) / 2;
    build2(2 * id, l, mid); build2(2 * id + 1, mid + 1, r);
    adj[4 * n + 2 * id].pb(4 * n + id);
    rev[4 * n + id].pb(4 * n + 2 * id);
    adj[4 * n + 2 * id + 1].pb(4 * n + id);
    rev[4 * n + id].pb(4 * n + 2 * id + 1);
}
void add_edge2(ll id, ll l, ll r, ll left, ll right, ll v){ 
    if(l > right || r < left) return;
    if(left <= l && r <= right){
        adj[8 * n + v].pb(id);
        rev[id].pb(8 * n + v);
        return;
    }
    ll mid = (l + r) / 2;
    add_edge2(2 * id, l, mid, left, right, v);
    add_edge2(2 * id + 1, mid + 1, r, left, right, v);
}
void to_thic_cau(){
	cin >> n;
	build1(1,1,n); build2(1,1,n);
	for(int i = 1; i <= n;i++){
		ll l,r; cin >> l >> r;
		add_edge2(1,1,n,l,r,i);
	}
	dijk(8 * n + 1, 0); dijk(9 * n, 1); finalize();
    cin >> q;
    while(q--){
        ll x; cin >> x;
        cout << (dp[8 * n + x] >= inf ? -1 : dp[8 * n + x]) << "\n";
    }
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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