oj.uz

Submission #116532

# Submission time Handle Problem Language Result Execution time Memory
116532 2019-06-12T18:25:40 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
5 / 100
 3 ms 580 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=100;
int n, k, q, l[mxN], d[mxN][mxN];
vector<int> adj[mxN];
queue<int> qu;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> q;
	for(int i=0; i<n; ++i) {
		cin >> l[i];
		int mx=0;
		for(int j=i-1; ~j; --j) {
			if(mx<l[i]&&mx<l[j]) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
			mx=max(l[j], mx);
		}
	}
	memset(d, 0x3f, sizeof(d));
	for(int i=0; i<n; ++i) {
		d[i][i]=0;
		qu.push(i);
		while(qu.size()) {
			int u=qu.front();
			qu.pop();
			for(int v : adj[u]) {
				if(d[i][v]>d[i][u]+1) {
					d[i][v]=d[i][u]+1;
					qu.push(v);
				}
			}
		}
	}
	for(int a, b; q--; ) {
		cin >> a >> b, --a, --b;
		cout << d[a][b]-1 << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -