Submission #963227

#	Time	Username	Problem	Language	Result	Execution time	Memory
963227		dorulean	Passport (JOI23_passport)	C++17	100 / 100	667 ms	86828 KiB

passport

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define eb emplace_back

const int N = 2e5 + 5;
const int Inf = 0x3f3f3f3f;
int st[N], dr[N], n, q, x;
int dp[4 * N], dpl[4 * N], dpr[4 * N];
int sgt[4 * N];
vpii g[4 * N];

void build(int x, int l, int r) {
	if (l == r) {
		sgt[x] = l;
		return;
	}
	sgt[x] = x + n;
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	g[sgt[x << 1]].eb(sgt[x], 0);
	g[sgt[x << 1 | 1]].eb(sgt[x], 0);
}

void update(int x, int l, int r, int i) {
	if (st[i] <= l && r <= dr[i]) {
		g[sgt[x]].eb(i, 1);
		return;
	}
	int mid = (l + r) >> 1;
	if (st[i] <= mid)
		update(x << 1, l, mid, i);
	if (mid + 1 <= dr[i])
		update(x << 1 | 1, mid + 1, r, i);
}

void dijkstra(int* dp) {
	priority_queue<pii,vpii,greater<pii>> q;
	for (int i = 1; i <= n; ++i) {
		if (dp[i] < Inf) {
			q.emplace(dp[i], i);
		}
	}
	for (int i = n + 1; i <= 4 * n; ++i)
		dp[i] = Inf;
	while (!q.empty()) {
		int curr = q.top().first, u = q.top().second;
		q.pop();
		if (curr > dp[u]) continue;
		for (auto it : g[u])
			if (dp[it.first] > dp[u] + it.second) {
				dp[it.first] = dp[u] + it.second;
				q.emplace(dp[it.first], it.first);
			}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

 	cin >> n;
 	build(1, 1, n);
 
 	for (int i = 1; i <= n; ++i) {
 		cin >> st[i] >> dr[i];
 		dpl[i] = (st[i] == 1 ? 1 : Inf);
 		dpr[i] = (dr[i] == n ? 1 : Inf);
 		update(1, 1, n, i);
 	}
 	
 	dijkstra(dpl);
 	dijkstra(dpr);
 	
 	for (int i = 1; i <= n; ++i)
 		dp[i] = min(Inf, dpl[i] + dpr[i]);
 	
 	dijkstra(dp);
 	
 	for (cin >> q; q; --q) {
 		cin >> x;
 		cout << (dp[x] == Inf ? -1 : dp[x] - 1) << '\n';
 	}
} 

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