Submission #549084

#	Time	Username	Problem	Language	Result	Execution time	Memory
549084		LucaDantas	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2055 ms	9428 KiB

railway_trip

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

namespace siuu {
	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;
		}
	}

	void brute(int n, int k, int 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);
		}
	}
}

constexpr int maxn = 1e5+10, maxk = 21;

int a[maxn], l[maxn][2], r[maxn][2], dist[2][maxn], mark[maxn], seen[maxn], cnt;

vector<int> pos[maxk];

int d(int x, int y, int k) {
	// se x==y ele retorna -1 e é pra retornar isso mesmo
	if(x > y) swap(x, y);
	return lower_bound(pos[k].begin(), pos[k].end(), y) - lower_bound(pos[k].begin(), pos[k].end(), x) - 1;
}

vector<int> reached[2][maxk];

void dijkstra(int s, int k) {
	++cnt;
	dist[k][s] = 0;
	seen[s] = cnt;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0, s});
	while(q.size()) {
		int u = q.top().second; q.pop();
		if(mark[u] == cnt) continue;
		mark[u] = cnt;
		reached[k][a[u]].push_back(u);

		int d = dist[k][u];
		for(auto [v, w] : {make_pair(l[u][0], l[u][1]), make_pair(r[u][0], r[u][1])}) {
			if(seen[v] < cnt || dist[k][v] > d + w) {
				seen[v] = cnt;
				dist[k][v] = d+w;
				q.push({d+w, v});
			}
		}
	}
}

int main() {
	int n, k, q; scanf("%d %d %d", &n, &k, &q);
	if(k > 20) return siuu::brute(n, k, q), 0;
	for(int i = 0; i < n; i++) {
		scanf("%d", a+i);
		for(int j = 0; j <= a[i]; j++)
			pos[j].push_back(i);
	}

	for(int i = 0; i < n; i++) {
		if(a[i] == k) { l[i][0] = i; l[i][1] = 0; continue; }
		l[i][0] = i-1; l[i][1] = 1;
		while(a[l[i][0]] <= a[i]) {
			l[i][1] = (a[l[i][0]] == a[i] ? l[l[i][0]][1] : 0) + 1;
			l[i][0] = l[l[i][0]][0];
		}
	}
	
	for(int i = n-1; i >= 0; i--) {
		if(a[i] == k) { r[i][0] = i, r[i][1] = 0; continue; }
		r[i][0] = i+1; r[i][1] = 1;
		while(a[r[i][0]] <= a[i]) {
			r[i][1] = (a[r[i][0]] == a[i] ? r[r[i][0]][1] : 0) + 1;
			r[i][0] = r[r[i][0]][0];
		}
	}

	while(q--) {
		int x, y; scanf("%d %d", &x, &y);
		--x, --y;

		dijkstra(x, 0); dijkstra(y, 1);

		int ans = 0x3f3f3f3f;

		for(int lvl = 1; lvl <= k; lvl++) {
			for(int x : reached[0][lvl]) for(int y : reached[1][lvl])
				ans = min(ans, dist[0][x] + dist[1][y] + d(x, y, lvl));
			reached[0][lvl].clear(), reached[1][lvl].clear();
		}

		printf("%d\n", ans);
	}
}

Compilation message (stderr)

railway_trip.cpp: In function 'void siuu::brute(int, int, int)':
railway_trip.cpp:26:9: 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:19: 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);
      |              ~~~~~^~~~~~~~~~~~~~~~~
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:89:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  int n, k, q; scanf("%d %d %d", &n, &k, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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