Submission #727414

#	Time	Username	Problem	Language	Result	Execution time	Memory
727414		model_code	Passport (JOI23_passport)	C++17	100 / 100	531 ms	49224 KiB

passport

/*
	FULL-SCORE SOLUTION OF "PASSPORT"
	- The way of implementation is a bit different from official review
		- It does not create graph explicitly
		- It uses Dijkstra's algorithm instead of BFS, but the time complexity does not change in this implementation
	- Time Complexity: O(N log N)
*/

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class state {
public:
	int pos, cost;
	state() : pos(-1), cost(0) {}
	state(int pos_, int cost_) : pos(pos_), cost(cost_) {}
	bool operator<(const state& s) const {
		return cost > s.cost;
	}
};

vector<int> solve(int N, int Q, const vector<int>& L, const vector<int>& R, const vector<int>& X) {
	const int INF = 1012345678;

	// step #1. do segment-tree-like precalculation
	int sz = 1;
	while (sz < N) {
		sz *= 2;
	}
	vector<vector<int> > dat(sz * 2);
	for (int i = 0; i < N; i++) {
		int cl = L[i] + sz;
		int cr = R[i] + sz;
		while (cl != cr) {
			if (cl & 1) {
				dat[cl++].push_back(i);
			}
			if (cr & 1) {
				dat[--cr].push_back(i);
			}
			cl >>= 1;
			cr >>= 1;
		}
	}

	// step #2. function to calculate distance
	auto calc = [&](const vector<int>& initial_dist) {
		vector<int> dist = initial_dist;
		priority_queue<state> que;
		for (int i = 0; i < N; i++) {
			if (dist[i] != INF) {
				que.push(state(i, dist[i]));
			}
		}
		vector<bool> vis(N, false);
		vector<bool> used(sz * 2, false);
		while (!que.empty()) {
			int u = que.top().pos;
			que.pop();
			if (!vis[u]) {
				vis[u] = true;
				int idx = u + sz;
				while (idx >= 1 && !used[idx]) {
					for (int j : dat[idx]) {
						if (dist[j] > dist[u] + 1) {
							dist[j] = dist[u] + 1;
							que.push(state(j, dist[j]));
						}
					}
					used[idx] = true;
					idx >>= 1;
				}
			}
		}
		return dist;
	};

	// step #3. main part
	vector<int> ini1(N, INF); ini1[0] = 0;
	vector<int> ini2(N, INF); ini2[N - 1] = 0;
	vector<int> d1 = calc(ini1); d1[0] = 1;
	vector<int> d2 = calc(ini2); d2[N - 1] = 1;
	vector<int> ini3(N);
	for (int i = 0; i < N; i++) {
		ini3[i] = min(d1[i] + d2[i], INF);
	}
	vector<int> d3 = calc(ini3);
	vector<int> answer(Q);
	for (int i = 0; i < Q; i++) {
		answer[i] = (d3[X[i]] != INF ? d3[X[i]] - 1 : -1);
	}

	return answer;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> L(N), R(N);
	for (int i = 0; i < N; i++) {
		cin >> L[i] >> R[i];
		L[i] -= 1;
	}
	int Q;
	cin >> Q;
	vector<int> X(Q);
	for (int i = 0; i < Q; i++) {
		cin >> X[i];
		X[i] -= 1;
	}
	vector<int> res = solve(N, Q, L, R, X);
	for (int i = 0; i < Q; i++) {
		cout << res[i] << '\n';
	}
	return 0;
}

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