Submission #796748

#	Time	Username	Problem	Language	Result	Execution time	Memory
796748		GusterGoose27	Passport (JOI23_passport)	C++17	100 / 100	664 ms	74516 KiB

passport

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 2e5+5;
const int inf = 1e9;
 
typedef pair<int, int> pii;
 
int dist[2][2*MAXN];
int sumdist[2*MAXN];
int n;
 
vector<pii> edges[2*MAXN];
 
void build() {
	for (int i = 1; i < n; i++) {
		edges[2*i].push_back(pii(i, 0));
		edges[2*i+1].push_back(pii(i, 0));
	}
}

void assign(int i, int l, int r) {
	for (; r > l; l /= 2, r /= 2) {
		if (l & 1) edges[l++].push_back(pii(i, 1));
		if (r & 1) edges[--r].push_back(pii(i, 1));
	}
}
 
void dijkstra(int curdist[]) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < 2*n; i++)
		pq.push(pii(curdist[i], i));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		int cur = tp.second;
		if (tp.first > curdist[cur]) continue;
		for (pii p: edges[cur]) {
			int nxtdist = tp.first+p.second;
			if (nxtdist < curdist[p.first]) {
				curdist[p.first] = nxtdist;
				pq.push(pii(nxtdist, p.first));
			}
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	build();
	fill(dist[0], dist[0]+2*n, inf);
	fill(dist[1], dist[1]+2*n, inf);
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		l--; r--;
		assign(i+n, l+n, r+n+1);
		if (l == 0) dist[0][i+n] = 0;
		if (r == n-1) dist[1][i+n] = 0;
	}
	dijkstra(dist[0]);
	dijkstra(dist[1]);
	for (int i = 0; i < 2*n; i++) {
		sumdist[i] = (i < n) ? inf : min(inf, dist[0][i]+dist[1][i]);
	}
	// for (int i = n; i < 2*n; i++) cerr << sumdist[i] << '\n';
	dijkstra(sumdist);
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int s; cin >> s; s += n-1;
		// cerr << dist[0][s] << ' ' << dist[1][s] << '\n';
		cout << ((sumdist[s] < inf) ? sumdist[s]+1 : -1) << '\n';
	}
}

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