제출 #766501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766501		MetalPower	Passport (JOI23_passport)	C++14	100 / 100	419 ms	41404 KiB

passport

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int INF = 1e9 + 7;
const int MX = 2e5 + 10;

int N, Q, l[MX], r[MX], dist[MX][4];
bool vis[MX];

struct segtree{
	vector<int> st[MX << 1];

	void reset(){
		for(int i = 0; i < (MX << 1); i++) st[i].clear();
	}

	void upd(int l, int r, int v){
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1){
				st[l].push_back(v);
				l++;
			}
			if(r & 1){
				--r;
				st[r].push_back(v);
			}
		}
	}

	vector<int> que(int p){
		vector<int> res;
		for(p += MX; p > 0; p >>= 1){
			for(int x : st[p]){
				if(!vis[x]){
					vis[x] = true;
					res.push_back(x);
				}
			}
			st[p].clear();
		}
		return res;
	}
} S;

void bfs1(){

	queue<int> q;
	dist[0][0] = 0; vis[0] = 1; q.push(0);

	for(; !q.empty(); ){
		int cd = q.front(); q.pop();

		vector<int> adj = S.que(cd);

		/*
		cout << "next of " << cd << " := ";
		for(int nx : adj) cout << nx << " ";
		cout << '\n';
		*/

		for(int nx : adj){
			dist[nx][0] = dist[cd][0] + 1;
			q.push(nx);
		}
	}
}

void bfs2(){

	queue<int> q;
	dist[N - 1][1] = 0; vis[N - 1] = 1; q.push(N - 1);

	for(; !q.empty(); ){
		int cd = q.front(); q.pop();

		vector<int> adj = S.que(cd);

		/*
		cout << "next of " << cd << " := ";
		for(int nx : adj) cout << nx << " ";
		cout << '\n';
		*/

		for(int nx : adj){
			dist[nx][1] = dist[cd][1] + 1;
			q.push(nx);
		}
	}
}

priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(){

	for(int i = 0; i < N; i++){
		if(i == 0){
			if(dist[i][1] != INF){
				dist[i][2] = dist[i][1];
				pq.push({dist[i][1], i});
			}
		}else if(i == N - 1){
			if(dist[i][0] != INF){
				dist[i][2] = dist[i][0];
				pq.push({dist[i][0], i});
			}
		}else{
			if(dist[i][0] != INF && dist[i][1] != INF){
				dist[i][2] = dist[i][0] + dist[i][1] - 1;
				pq.push({dist[i][0] + dist[i][1] - 1, i});
			}
		}
	}

	for(; !pq.empty(); ){
		int cdist = pq.top().fi, cnode = pq.top().se; pq.pop();
		if(dist[cnode][2] < cdist) continue;

		vector<int> adj = S.que(cnode);
		for(int nx : adj){
			if(dist[nx][2] > cdist + 1){
				dist[nx][2] = cdist + 1;
				pq.push({dist[nx][2], nx});
			}
		}
	}
}

void init(){
	S.reset();
	for(int i = 0; i < N; i++){
		S.upd(l[i], r[i], i);
		vis[i] = 0;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> l[i] >> r[i]; l[i]--, r[i]--;
		S.upd(l[i], r[i], i);
	}

	for(int i = 0; i < MX; i++) dist[i][0] = dist[i][1] = dist[i][2] = dist[i][3] = INF;

	init();
	bfs1();

	init();
	bfs2();

	init();
	dijkstra();

	cin >> Q;
	for(int i = 0; i < Q; i++){
		int v; cin >> v; v--;
		int ans = dist[v][2];
		if(ans >= INF) cout << -1 << '\n';
		else cout << ans << '\n';
	}
}

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