oj.uz

Submission #117413

# Submission time Handle Problem Language Result Execution time Memory
117413 2019-06-15T21:57:36 Z Mamnoon_Siam Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 7928 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

int n, k, q;
vector<int> g[maxn];
int lvl[maxn];
int a[maxn];

int dist(int s, int t) {
	memset(lvl, -1, sizeof lvl);
	queue<int> Q;
	lvl[s] = 0;
	Q.emplace(s);
	while(Q.size()) {
		int u = Q.front();
		Q.pop();
		for(int v : g[u]) {
			if(!~lvl[v]) {
				lvl[v] = lvl[u] + 1;
				Q.emplace(v);
			}
		}
	}
	return lvl[t];
}

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(a[j] >= a[i]) {
				g[i].emplace_back(j);
				g[j].emplace_back(i);
				break;
			}
		}
		for(int j = i - 1; j >= 1; j--) {
			if(a[j] >= a[i]) {
				g[i].emplace_back(j);
				g[j].emplace_back(i);
				break;
			}
		}
	}
	while(q--) {
		int s, t;
		cin >> s >> t;
		cout << dist(s, t) - 1 << endl;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 226 ms 7360 KB Output is correct
3 Correct 248 ms 7544 KB Output is correct
4 Correct 248 ms 7544 KB Output is correct
5 Correct 212 ms 7544 KB Output is correct
6 Correct 207 ms 7672 KB Output is correct
7 Correct 210 ms 7928 KB Output is correct
8 Correct 90 ms 6980 KB Output is correct
9 Correct 1181 ms 7704 KB Output is correct
10 Correct 1008 ms 7304 KB Output is correct
11 Correct 735 ms 7752 KB Output is correct
12 Correct 697 ms 7928 KB Output is correct
13 Correct 741 ms 7624 KB Output is correct
14 Correct 697 ms 7672 KB Output is correct
15 Correct 1074 ms 7648 KB Output is correct
16 Correct 702 ms 7672 KB Output is correct
17 Correct 217 ms 7928 KB Output is correct
18 Correct 223 ms 7928 KB Output is correct
19 Correct 147 ms 7800 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 7160 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 2054 ms 7288 KB Time limit exceeded
2 Halted 0 ms 0 KB -