Submission #116532

#	Time	Username	Problem	Language	Result	Execution time	Memory
116532		tmwilliamlin168	Railway Trip (JOI17_railway_trip)	C++14	5 / 100	3 ms	580 KiB

railway_trip

#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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55