Submission #549007

#	Time	Username	Problem	Language	Result	Execution time	Memory
549007		LucaDantas	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2059 ms	3284 KiB

railway_trip

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

constexpr int maxn = 1e5+10;

int a[maxn], l[maxn], r[maxn], dist[2][maxn];

void bfs(int s, int k) {
	for(int i = 0; i < maxn; i++)
		dist[k][i] = 0x3f3f3f3f;
	dist[k][s] = 0;
	queue<int> q;
	q.push(s);
	while(q.size()) {
		int u = q.front(); int d = dist[k][u];
		q.pop();
		for(int rep = 0; rep < 2; rep++, swap(l[u], r[u]))
			if(dist[k][l[u]] > d+1)
				q.push(l[u]), dist[k][l[u]] = d+1;
	}
}

int main() {
	int n, k, q; scanf("%d %d %d", &n, &k, &q);
	for(int i = 0; i < n; i++)
		scanf("%d", a+i);
	l[0] = 0;
	for(int i = 1; i < n; i++) {
		l[i] = i-1;
		while(a[l[i]] < a[i])
			l[i] = l[l[i]];
	}
	r[n-1] = n-1;
	for(int i = n-2; i >= 0; i--) {
		r[i] = i+1;
		while(a[r[i]] < a[i])
			r[i] = r[r[i]];
	}
	while(q--) {
		int x, y; scanf("%d %d", &x, &y);
		--x, --y;
		bfs(x, 0); bfs(y, 1);
		int ans = 0x3f3f3f3f;
		for(int i = 0; i < n; i++)
			ans = min(ans, dist[0][i] + dist[1][i] - 1);
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:24:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  int n, k, q; scanf("%d %d %d", &n, &k, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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