제출 #1278231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278231		namhh	Passport (JOI23_passport)	C++20	100 / 100	707 ms	74768 KiB

passport

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,q,val[N],l[N],r[N],d[4*N][3];
vector<pii>adj[4*N];
void build(int id, int l, int r){
	if(l == r){
		val[l] = id;
		return;
	}
	int mid = (l+r)/2;
	build(2*id,l,mid);
	build(2*id+1,mid+1,r);
	adj[2*id].push_back({id,0});
	adj[2*id+1].push_back({id,0});
}
void add(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		adj[id].push_back({val,1});
		return;
	}
	int mid = (l+r)/2;
	add(2*id,l,mid,u,v,val);
	add(2*id+1,mid+1,r,u,v,val);
}
void bfs(int type){
	for(int i = 1; i <= 4*n; i++) d[i][type] = 1e9;
	deque<int>dq;
	if(type == 0){
		d[val[1]][0] = 0;
		dq.push_front(val[1]);
	}
	else{
		d[val[n]][1] = 0;
		dq.push_front(val[n]);
	}
	while(!dq.empty()){
		int u = dq.front();
		dq.pop_front();
		for(auto[v,w]: adj[u]){
			if(w == 0){
				if(d[v][type] > d[u][type]){
					d[v][type] = d[u][type];
					dq.push_front(v);
				}
			}
			else{
				if(d[v][type] > d[u][type]+1){
					d[v][type] = d[u][type]+1;
					dq.push_back(v);
				}
			}
		}
	}
}
void dijkstra(){
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i = 1; i <= 4*n; i++) d[i][2] = 1e9;
	for(int i = 1; i <= n; i++){
		d[val[i]][2] = d[val[i]][0]+d[val[i]][1];
		if(i != 1 && i != n) d[val[i]][2]--;
		pq.push({d[val[i]][2],val[i]});
	}
	while(!pq.empty()){
		auto[c,u] = pq.top();
		pq.pop();
		if(c > d[u][2]) continue;
		for(auto[v,w]: adj[u]){
			if(d[v][2] > d[u][2]+w){
				d[v][2] = d[u][2]+w;
				pq.push({d[v][2],v});
			}
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	build(1,1,n);
	for(int i = 1; i <= n; i++){
		cin >> l[i] >> r[i];
		add(1,1,n,l[i],r[i],val[i]);
	}
	bfs(0);
	bfs(1);
	dijkstra();
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		if(d[val[x]][2] > 1e8) cout << -1 << "\n";
		else cout << d[val[x]][2] << "\n";
	}
}

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