제출 #1139659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139659		LCJLY	Passport (JOI23_passport)	C++20	0 / 100	427 ms	140556 KiB

passport

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<pii>adj[800005];
int ptr=0;

struct node{
	int s,e,m;
	node *l,*r;
	int index=0;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		index=ptr++;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			//adj[index].push_back({l->index,0});
			adj[l->index].push_back({index,0});
			//adj[index].push_back({r->index,0});
			adj[r->index].push_back({index,0});
		}
		else{
			//adj[index].push_back({s,0});
			adj[s].push_back({index,0});
		}
	}
	
	void rangeEdge(int x, int y, int c){
		if(x<=s&&y>=e){
			//adj[c].push_back({index,1});
			adj[index].push_back({c,1});
			return;
		}
		if(x<=m) l->rangeEdge(x,y,c);
		if(y>m) r->rangeEdge(x,y,c);
	}
};

void solve(){
	int n;
	cin >> n;
	pii arr[n+5];
	for(int x=1;x<=n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	ptr=n+1;
	node st(1,n);
	//ptr=n+1;
	
	for(int x=1;x<=n;x++){
		st.rangeEdge(arr[x].first,arr[x].second,x);
	}
	
	int dist[ptr+5];
	memset(dist,-1,sizeof(dist));
	deque<pii>de;
	for(int x=1;x<=n;x++){
		if(arr[x].first==1){
			dist[x]=0;
			de.push_back({0,x});
		}
	}

	while(!de.empty()){
		pii cur=de.front();
		de.pop_front();
		int index=cur.second;
		int d=cur.first;
		if(dist[index]!=d) continue;
		for(auto it:adj[index]){
			int nx=it.first;
			int nd=d+it.second;
			if(dist[nx]!=-1&&dist[nx]<=nd) continue;
			dist[nx]=nd;
			if(it.second==0) de.push_front({nd,nx});
			else de.push_back({nd,nx});
		}
	}
	
	int dist2[ptr+5];
	memset(dist2,-1,sizeof(dist2));
	for(int x=1;x<=n;x++){
		if(arr[x].first==n){
			dist2[x]=0;
			de.push_back({0,x});
		}
	}
	
	while(!de.empty()){
		pii cur=de.front();
		de.pop_front();
		int index=cur.second;
		int d=cur.first;
		if(dist2[index]!=d) continue;
		for(auto it:adj[index]){
			int nx=it.first;
			int nd=d+it.second;
			if(dist2[nx]!=-1&&dist2[nx]<=nd) continue;
			dist2[nx]=nd;
			if(it.second==0) de.push_front({nd,nx});
			else de.push_back({nd,nx});
		}
	}
	
	int dist3[ptr+5];
	memset(dist3,-1,sizeof(dist3));
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int x=1;x<=n;x++){
		if(dist[x]==-1||dist2[x]==-1) continue;
		dist3[x]=dist[x]+dist2[x];
		pq.push({dist3[x],x});
	}
	
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int d=cur.first;
		int index=cur.second;
		if(dist3[index]!=d) continue;
		for(auto it:adj[index]){
			int nx=it.first;
			int nd=it.second+d;
			if(dist3[nx]!=-1&&dist3[nx]<=nd) continue;
			dist3[nx]=nd;
			pq.push({nd,nx});
		}
	}
	
	//debug
	//for(int x=1;x<=ptr;x++){
		//cout << dist[x] << " ";
	//}
	//cout << " dist\n";
	//for(int x=1;x<=ptr;x++){
		//cout << dist2[x] << " ";
	//}
	//cout << " dist2\n";
	//for(int x=1;x<=ptr;x++){
		//cout << dist3[x] << " ";
	//}
	//cout << " dist3\n";
	
	int q;
	cin >> q;
	int temp;
	
	for(int x=0;x<q;x++){
		cin >> temp;
		cout << dist3[temp] << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;	
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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