oj.uz

Submission #210510

# Submission time Handle Problem Language Result Execution time Memory
210510 2020-03-17T14:30:18 Z hanagasumi Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 16496 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;
typedef long double ld;

int inf = 1e9 + 100;

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, k, q;
	cin >> n >> k >> q;
	vector<int> l(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}

	vector<int> pred(n, -1);
	vector<int> nxt(n, n);
	vector<pair<int, int>> have;
	for (int i = 0; i < n; i++) {
		while(len(have) > 0 && have.back().ft <= l[i]) 
			have.pop_back();
		if(len(have) > 0) 
			pred[i] = have.back().sc;
		have.pb({l[i], i});
	}
	have.clear();
	for (int i = n - 1; i >= 0; i--) {
		while(len(have) > 0 && have.back().ft <= l[i]) 
			have.pop_back();
		if(len(have) > 0)
			nxt[i] = have.back().sc;
		have.pb({l[i], i});
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if(i < n - 1) 
			g[i].pb(i + 1);
		int now = i - 1;
		while(1) {
			if(now < 0) 
				break;
			g[i].pb(now);
			cnt++;
			if(l[now] >= l[i]) 
				break;
			now = pred[now];
		}
		now = i + 1;
		while(1) {
			if(now >= n) 
				break;
			g[i].pb(now);
			cnt++;
			if(l[now] >= l[i]) 
				break;
			now = nxt[now];
		}
	}
	if(cnt > 5 * n) 
		return -1;

	for (int i = 0; i < q; i++) {		
		int a, b;
		cin >> a >> b;
		a--, b--;

		unordered_map<int, int> dst;
		dst[a] = 0;
		deque<int> q;
		q.pb(a);
		while(len(q) > 0) {
			if(dst.count(b))
				break;
			auto now = q.front();
			q.pop_front();
			for (auto x : g[now]) {
				if(dst.count(b))
					break;
				if(dst.count(x)) 
					continue;
				dst[x] = dst[now] + 1;
				q.pb(x);
			}
		}
		cout << dst[b] - 1 << '\n';
	}

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 570 ms 15504 KB Output is correct
3 Correct 556 ms 15500 KB Output is correct
4 Correct 615 ms 15780 KB Output is correct
5 Correct 620 ms 15852 KB Output is correct
6 Correct 632 ms 15936 KB Output is correct
7 Correct 685 ms 16264 KB Output is correct
8 Correct 448 ms 13940 KB Output is correct
9 Correct 535 ms 15660 KB Output is correct
10 Correct 467 ms 14892 KB Output is correct
11 Correct 585 ms 15124 KB Output is correct
12 Correct 560 ms 14948 KB Output is correct
13 Correct 590 ms 15128 KB Output is correct
14 Correct 560 ms 15052 KB Output is correct
15 Correct 576 ms 15140 KB Output is correct
16 Correct 530 ms 15056 KB Output is correct
17 Correct 780 ms 16276 KB Output is correct
18 Correct 695 ms 16256 KB Output is correct
19 Correct 577 ms 15708 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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