oj.uz

Submission #549084

# Submission time Handle Problem Language Result Execution time Memory
549084 2022-04-15T06:00:37 Z LucaDantas Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 9428 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 15 ms 6048 KB Output is correct
3 Correct 20 ms 8288 KB Output is correct
4 Correct 21 ms 2228 KB Output is correct
5 Correct 19 ms 2236 KB Output is correct
6 Correct 18 ms 2268 KB Output is correct
7 Correct 17 ms 2752 KB Output is correct
8 Correct 114 ms 2444 KB Output is correct
9 Correct 74 ms 2784 KB Output is correct
10 Correct 86 ms 2648 KB Output is correct
11 Correct 70 ms 2832 KB Output is correct
12 Correct 66 ms 2772 KB Output is correct
13 Correct 73 ms 2796 KB Output is correct
14 Correct 73 ms 2848 KB Output is correct
15 Correct 71 ms 2832 KB Output is correct
16 Correct 69 ms 2688 KB Output is correct
17 Correct 17 ms 2832 KB Output is correct
18 Correct 17 ms 2772 KB Output is correct
19 Correct 16 ms 2744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 7956 KB Output is correct
2 Correct 241 ms 7188 KB Output is correct
3 Correct 290 ms 8268 KB Output is correct
4 Correct 234 ms 8448 KB Output is correct
5 Correct 236 ms 8772 KB Output is correct
6 Correct 269 ms 9092 KB Output is correct
7 Correct 261 ms 9428 KB Output is correct
8 Correct 168 ms 5416 KB Output is correct
9 Correct 136 ms 5320 KB Output is correct
10 Correct 375 ms 5320 KB Output is correct
11 Correct 425 ms 5360 KB Output is correct
12 Correct 415 ms 5444 KB Output is correct
13 Correct 425 ms 5304 KB Output is correct
14 Correct 437 ms 5180 KB Output is correct
15 Correct 618 ms 5348 KB Output is correct
16 Correct 591 ms 7368 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -