Submission #1186149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186149		dubabuba	Railway Trip (JOI17_railway_trip)	C++20	20 / 100	2095 ms	56432 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 1e6 + 10;
int a[mxn], n, k, q;
int mn[mxn], mx[mxn];
vector<int> ind[mxn];
vector<int> adj[mxn];

int fmax(int u) { return mx[u] == u ? u : mx[u] = fmax(mx[u]); }
int fmin(int u) { return mn[u] == u ? u : mn[u] = fmin(mn[u]); }

int dis[mxn];
int djkstra(int st, int en) {
	for(int i = 1; i <= n; i++)
		dis[i] = -1;

	priority_queue<pii> pq;
	pq.push(MP(0, st));

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

		if(u == en) return d;
		if(dis[u] > -1) continue;
		dis[u] = d;

		for(int v : adj[u]) {
			if(dis[v] == -1)
				pq.push(MP(-d - 1, v));
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		mn[i] = mx[i] = i;

		ind[a[i]].push_back(i);
	}

	mn[n + 1] = mx[n + 1] = 1;

	for(int x = 1; x < k; x++) {
		for(int i : ind[x]) {
			mn[i] = i - 1;
			mx[i] = i + 1;
		}

		int prv = -1;
		for(int i : ind[x]) {
			if(prv >= i) continue;
			int L = fmin(i);
			int R = fmax(i);

			adj[L].push_back(R);
			adj[R].push_back(L);
			prv = R;
		}
	}

	for(int i = 1; i < n; i++) {
		adj[i].push_back(i + 1);
		adj[i + 1].push_back(i);
	}

	for(int i = 0; i < q; i++) {
		int u, v;
		cin >> u >> v;
		cout << djkstra(u, v) - 1 << endl;
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55