Submission #744695

#	Time	Username	Problem	Language	Result	Execution time	Memory
744695		emptypringlescan	Passport (JOI23_passport)	C++17	100 / 100	1269 ms	145780 KiB

passport

#include <bits/stdc++.h>
using namespace std;
int cnd;
vector<pair<int,int> > adj[800005];
struct node{
	int s,e,m;
	int nd;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		nd=cnd;
		cnd++;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			adj[l->nd].push_back({nd,0});
			adj[r->nd].push_back({nd,0});
		}
		else{
			adj[s].push_back({nd,0});
		}
	}
	void addedge(int S, int E, int N){
		if(S<=s&&e<=E){
			adj[nd].push_back({N,1});
			return;
		}
		if(E<=m) l->addedge(S,E,N);
		else if(S>m) r->addedge(S,E,N);
		else{
			l->addedge(S,m,N);
			r->addedge(m+1,E,N);
		}
	}
} *root;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	cnd=n+1;
	root = new node(1,n);
	deque<pair<int,pair<int,int> > > dq;
	priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > pq;
	int dist[cnd][3];
	memset(dist,-1,sizeof(dist));
	for(int i=0; i<n; i++){
		int a,b;
		cin >> a >> b;
		root->addedge(a,b,i+1);
		if(a==1) dq.push_back({1,{1,i+1}});
		if(b==n) dq.push_back({1,{2,i+1}});
	}
	while(!dq.empty()){
		int a=dq.front().first,b=dq.front().second.first,c=dq.front().second.second;
		dq.pop_front();
		if(dist[c][b]!=-1) continue;
		dist[c][b]=a;
		for(auto i:adj[c]){
			if(dist[i.first][b]==-1){
				if(i.second==1) dq.push_back({a+i.second,{b,i.first}});
				else dq.push_front({a+i.second,{b,i.first}});
			}
		}
	}
	for(int i=1; i<=n; i++){
		//cout << dist[i][1] << ' ' << dist[i][2] << '\n';
		if(dist[i][1]!=-1&&dist[i][2]!=-1){
			pq.push({dist[i][1]+dist[i][2]-1,{0,i}});
		}
	}
	while(!pq.empty()){
		int a=pq.top().first,b=pq.top().second.first,c=pq.top().second.second;
		pq.pop();
		if(dist[c][b]!=-1) continue;
		dist[c][b]=a;
		for(auto i:adj[c]){
			if(dist[i.first][b]==-1) pq.push({a+i.second,{b,i.first}});
		}
	}
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		int x;
		cin >> x;
		cout << dist[x][0] << '\n';
	}
}

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