Submission #1011908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011908		pcc	Passport (JOI23_passport)	C++17	100 / 100	836 ms	213048 KiB

passport

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

#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
const int LEN = mxn*100;

int head[LEN],nid[LEN],to[LEN],wei[LEN];
int ecnt = 0,vcnt = 0;
int N,Q;

void add_edge(int a,int b){
	ecnt++;
	assert(ecnt<LEN);
	nid[ecnt] = head[a];
	head[a] = ecnt;
	to[ecnt] = b;
	return;
}

int newvertex(){
	return ++vcnt;
}

int seg[mxn*4];
pii arr[mxn];
int req[mxn];
int d1[LEN],d2[LEN];

void build(int now,int l,int r){
	if(l == r){
		seg[now] = l;
		return;
	}
	seg[now] = newvertex();
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	add_edge(seg[now*2+1],seg[now]);
	add_edge(seg[now*2+2],seg[now]);
}

void addseg(int now,int l,int r,int s,int e,int id){
	if(l>=s&&e>=r){
		add_edge(seg[now],id);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)addseg(now*2+1,l,mid,s,e,id);
	if(mid<e)addseg(now*2+2,mid+1,r,s,e,id);
	return;
}

namespace DIJKSTRA{
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	bitset<LEN> vis;
	void GO(int dist[]){
		vis.reset();
		for(int i = 1;i<=vcnt;i++)pq.push(pii(dist[i],i));
		while(!pq.empty()){
			auto [d,now] = pq.top();
			pq.pop();
			if(vis[now])continue;
			vis[now] = true;
			for(int eid = head[now];eid;eid = nid[eid]){
				int nxt = to[eid],w = wei[now];
				if(dist[nxt]>d+w){
					dist[nxt] = d+w;
					pq.push(pii(dist[nxt],nxt));
				}
			}
		}
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	vcnt = N;
	for(int i = 1;i<=N;i++)cin>>arr[i].fs>>arr[i].sc;
	cin>>Q;
	for(int i = 0;i<Q;i++)cin>>req[i];
	build(0,1,N);
	for(int i = 1;i<=N;i++){
		int id = newvertex();
		wei[id] = 1;
		addseg(0,1,N,arr[i].fs,arr[i].sc,id);
		add_edge(id,i);
	}
	fill(d1,d1+LEN,LEN);
	fill(d2,d2+LEN,LEN);
	d1[1] = d2[N] = 0;
	DIJKSTRA::GO(d1);
	DIJKSTRA::GO(d2);
	for(int i = 1;i<=vcnt;i++)d1[i] += d2[i];
	DIJKSTRA::GO(d1);
	for(int i = 0;i<Q;i++){
		auto re = d1[req[i]];
		cout<<(re>mxn?-1:re)<<'\n';
	}
	return 0;
}

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