제출 #1337587

#제출 시각아이디문제언어결과실행 시간메모리
1337587NAMINPassport (JOI23_passport)C++20
48 / 100
1286 ms1114112 KiB
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

struct Node{
	int l,r,d;
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N;
	cin >> N;
	vector<int> L(N),R(N);
	for(int i=0;i<N;i++){
		cin >> L[i] >> R[i];
		L[i]--,R[i]--;
	}
	int Q;
	cin >> Q;
	vector<int> X(Q);
	for(int i=0;i<Q;i++){
		cin >> X[i];
		X[i]--;
	}
	
	vector<vector<pair<int,int>>> mnl(N,vector<pair<int,int>>(N));
	vector<vector<pair<int,int>>> mxr(N,vector<pair<int,int>>(N));
	for(int i=0;i<N;i++){
		int l = L[i];
		int r = R[i];
		for(int j=i;j<N;j++){
			if(l>L[j]){
				l=L[j];
				r=R[j];
			}
			else if(l==L[j] && r<R[j]){
				r=R[j];
			}
			mnl[i][j]={l,r};
		}
	}
	for(int i=0;i<N;i++){
		int r = R[i];
		int l=L[i];
		for(int j=i;j<N;j++){
			if(r<R[j]){
				r=R[j];
				l=L[j];
			}
			if(r==R[j]&&l>L[j])
				l=L[j];
			mxr[i][j]={l,r};
		}
	}
	vector<Node> adj[N][N];
	for(int l=0;l<N;l++){
		for(int r=0;r<N;r++){
			int nxtl=mnl[l][r].first,nxtr=mnl[l][r].second;
			adj[min(l,nxtl)][max(r,nxtr)].push_back({l,r,1});
			nxtl=mxr[l][r].first,nxtr=mxr[l][r].second;
			adj[min(l,nxtl)][max(r,nxtr)].push_back({l,r,1});
			if(l<r){
				adj[l+1][r].push_back({l,r,0});
				adj[l][r-1].push_back({l,r,0});
			}
		}
	}

	vector<vector<int>> dist(N,vector<int>(N,1e9));
	vector<vector<int>> process(N,vector<int>(N,0));
	deque<Node> q;
	q.push_back({0,N-1,0});
	while(!q.empty()){
		int l=q.front().l,r=q.front().r,d=q.front().d;
		dist[l][r]=min(dist[l][r],d);
		q.pop_front();
		if(process[l][r])
			continue;
		process[l][r]=true;
		for(Node node : adj[l][r]){
			int nxtl=node.l,nxtr=node.r;
			int w = node.d;
			if(w==0)
				q.push_front({nxtl,nxtr,d});
			else
				q.push_back({nxtl,nxtr,d+1});
		}
		
	}
	for(int i=0;i<Q;i++){
		if(dist[X[i]][X[i]]!=1e9)
			cout << dist[X[i]][X[i]] << endl;
		else
			cout << -1 << endl;
	}
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...