답안 #117413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117413	2019-06-15T21:57:36 Z	Mamnoon_Siam	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2000 ms	7928 KB

railway_trip

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2063 ms	7160 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2054 ms	7288 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-