Submission #1154446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154446		beaboss	Passport (JOI23_passport)	C++20	100 / 100	1081 ms	115820 KiB

passport

// Source: 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 2e5 + 10;

vpii adj[6 * N];
vi d1(6 * N, N + 1);
vi dn(6 * N, N + 1);
vi db(6 * N, N + 1);

int n;

void connect(int ul, int ur, int node, int i = 1, int l = 1, int r = n+1) {
	if (r <= ul || ur <= l) return;
	if (r <= ur && l >= ul) {
		adj[i + 2*n].pb({node, 0});
		return;
	}
	int m = (l + r)/2;
	connect(ul, ur, node, 2*i, l, m);
	connect(ul, ur, node, 2*i+1, m, r);
}

void build(int i = 1, int l = 1, int r = n+1) {
	if (r - l == 1) {
		adj[l].pb({i + 2*n, 0});
		return;
	}
	int m = (l + r)/2;

	adj[2*i + 2*n].pb({i + 2*n, 0});
	adj[2*i+1 + 2*n].pb({i + 2*n, 0});

	build(2*i, l, m);
	build(2*i+1, m, r);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	build();
	vi all;
	FOR(i, 1, n+1) {
		adj[i + n].pb({i, 1});
		int l, r;
		cin >> l >> r;
		if (l == 1 && r == n) all.pb(i);
		connect(l, r+1, i+n);
	}

	deque<int> d;
	d.push_back(1);
	d1[1]=0;

	while (!d.empty()) {
		int cur = d.front();
		d.pop_front();
		for (auto val: adj[cur]) {
			if (d1[val.f] > d1[cur] + val.s) {
				d1[val.f] = d1[cur] + val.s;
				if (val.s == 0) d.push_front(val.f);
				else d.push_back(val.f);
			}
		}
	}

	d.push_back(n);
	dn[n]=0;

	while (!d.empty()) {
		int cur = d.front();
		d.pop_front();
		// cout << cur << dn[cur] << endl;
		for (auto val: adj[cur]) {
			if (dn[val.f] > dn[cur] + val.s) {
				dn[val.f] = dn[cur] + val.s;
				if (val.s == 0) d.push_front(val.f);
				else d.push_back(val.f);
			}
		}
	}

	priority_queue<pii> pq;

	FOR(i, 1, 6*n+1) {
		db[i]=d1[i] + dn[i];
		pq.push({-db[i], i});
	}

	while (!pq.empty()) {
		pii cur = pq.top();
		pq.pop();
		if (-cur.f != db[cur.s]) continue;
		for (auto val: adj[cur.s]) {
			if (db[val.f] > db[cur.s] + val.s) {
				db[val.f] = db[cur.s] + val.s;
				pq.push({-db[val.f], val.f});
			}
		}
	}

	



	int q;
	cin >> q;

	FOR(_, 0, q) {
		int x;
		cin >> x;
		int res = db[x];
		if (res > n) cout << -1 << endl;
		else cout << res << endl;
	}

}

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