Submission #1286695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286695		PlayVoltz	Passport (JOI23_passport)	C++20	100 / 100	1317 ms	182760 KiB

passport

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;

#define int long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, counter;
vector<vector<pii> > graph;

struct node{
	int s, e, m, val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if (s!=e){
			val=++counter;
			l = new node(s, m);
			r = new node(m+1, e);
			graph[l->val].pb(mp(val, 0));
			graph[r->val].pb(mp(val, 0));
		}
		else val=s;
	}
	void add(int left, int right, int v){
		if (s==left && e==right){
			graph[val].pb(mp(v, 1));
			return;
		}
		if (right<=m)l->add(left, right, v);
		else if (left>m)r->add(left, right, v);
		else l->add(left, m, v), r->add(m+1, right, v);
	}
}*st;

vector<int> bfs(int start){
	vector<int> dj(2*n, LLONG_MAX/2);
	deque<int> q(1, start);
	dj[start]=0;
	while(q.size()){
		int node=q[0];
		q.pop_front();
		for (auto num:graph[node])if(dj[node]+num.se<dj[num.fi]){
			dj[num.fi]=dj[node]+num.se;
			if (num.se)q.pb(num.fi);
			else q.push_front(num.fi);
		}
	}
	return dj;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a, b, q;
	cin>>n;
	counter=n;
	graph.resize(2*n);
	st = new node(1, n);
	for (int i=1; i<=n; ++i)cin>>a>>b, st->add(a, b, i);
	vector<int> d1=bfs(1), dn=bfs(n), ans(2*n, LLONG_MAX/2);
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for (int i=1; i<=n; ++i)if (d1[i]!=LLONG_MAX/2&&dn[i]!=LLONG_MAX/2)pq.push(mp(d1[i]+dn[i]-(i!=1&&i!=n), i));
	while (pq.size()){
		int node=pq.top().se, d=pq.top().fi;
		pq.pop();
		if (ans[node]<=d)continue;
		ans[node]=d;
		for (auto num:graph[node])pq.push(mp(num.se+d, num.fi));
	}
	cin>>q;
	while (q--)cin>>a, cout<<(ans[a]==LLONG_MAX/2?-1:ans[a])<<"\n";
}

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