Submission #1337541

#TimeUsernameProblemLanguageResultExecution timeMemory
1337541NAMINPassport (JOI23_passport)C++20
0 / 100
583 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];
			}
			else if(r==R[j]&&l>L[j])
				l=L[j];
			mxr[i][j]={l,r};
		}
	}

	vector<vector<int>> dist(N,vector<int>(N,1e9));
	vector<vector<int>> process(N,vector<int>(N,0));
	deque<Node> q;
	q.push_back({X[0],X[0],0});
	while(!q.empty()){
		int l=q.front().l,r=q.front().r,d=q.front().d;
		//cout << l << ' ' << r << endl;
		dist[l][r]=min(dist[l][r],d);
		//cout << l << ' ' << r << ' ' << d << endl;
		q.pop_front();
		if(process[l][r])
			continue;
		process[l][r]=true;
		int nxtl=mnl[l][r].first,nxtr=mnl[l][r].second;
		q.push_back({min(nxtl,l),max(nxtr,r),d+1});
		nxtl=mxr[l][r].first,nxtr=mxr[l][r].second;
		q.push_back({min(nxtl,l),max(nxtr,r),d+1});
	}
	if(dist[0][N-1]!=1e9)
		cout << dist[0][N-1] << 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...