QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #125072 | #365. Railway Trip | Adam_GS# | 5 | 1ms | 6556kb | C++17 | 872b | 2023-07-16 00:45:49 | 2024-07-04 00:43:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, INF=1e9+7;
vector<int>V[LIM];
int T[LIM], odl[LIM];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
rep(i, n) cin >> T[i];
rep(i, n) {
int akt=0;
for(int j=i+1; j<n; ++j) {
if(min(T[i], T[j])>akt) {
V[i].pb(j);
V[j].pb(i);
}
akt=max(akt, T[j]);
}
}
while(q--) {
int a, b;
cin >> a >> b; --a; --b;
rep(i, n) odl[i]=INF;
odl[a]=0;
queue<int>q;
q.push(a);
while(!q.empty()) {
int p=q.front(); q.pop();
for(auto i : V[p]) if(odl[i]==INF) {
odl[i]=odl[p]+1;
q.push(i);
}
}
cout << odl[b]-1 << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 5884kb
input:
100 100 50 100 86 39 28 49 22 79 14 83 100 15 26 37 51 53 18 74 15 96 72 47 80 10 46 62 88 20 36 46 29 40 28 37 88 91 41 24 63 14 92 24 31 99 61 62 96 94 51 51 21 72 97 59 96 97 94 66 88 32 96 58 26 53 1 100 31 85 30 42 69 40 62 54 94 49 62 13 20 82 74 20 44 54 69 65 34 78 64 48 69 19 35 8 92 100 87...
output:
3 1 3 5 3 3 3 0 2 5 2 6 1 3 1 3 5 5 3 5 4 7 3 6 3 4 4 4 7 0 2 3 2 4 5 5 6 5 5 6 4 3 2 4 5 2 5 4 2 2
result:
ok 50 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 6160kb
input:
100 100 50 100 85 82 7 50 49 51 45 30 3 29 99 71 93 5 68 70 52 12 44 1 35 99 80 76 34 23 28 62 91 80 77 59 57 30 15 23 13 16 21 58 23 38 49 44 73 7 47 24 53 97 83 14 71 16 75 61 24 17 96 51 41 74 53 25 2 42 36 73 57 53 45 10 12 11 79 68 2 78 44 47 67 21 99 25 68 60 71 23 92 9 2 97 37 43 64 32 28 7 1...
output:
2 0 5 4 2 4 2 4 3 5 4 3 3 6 4 4 3 3 3 4 2 3 3 3 4 5 5 2 3 3 5 4 3 4 2 2 3 5 3 6 2 5 4 2 2 4 4 3 4 7
result:
ok 50 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 6556kb
input:
100 100 50 100 56 83 81 2 73 24 77 19 11 79 100 36 32 62 4 41 50 51 62 68 6 11 36 28 21 61 82 72 86 35 93 94 87 50 14 77 83 14 49 95 32 5 20 59 55 77 31 52 70 23 81 4 10 34 100 4 67 60 1 23 26 65 1 30 96 43 49 70 81 18 82 97 80 62 28 93 38 91 39 67 6 17 78 60 60 55 97 45 58 44 80 24 91 14 5 35 93 25...
output:
4 4 4 5 3 3 3 4 2 4 2 5 4 3 4 3 5 4 5 3 3 2 4 1 3 4 3 3 5 2 5 5 5 0 3 3 3 2 4 1 5 2 4 3 0 5 4 5 4 3
result:
ok 50 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 6396kb
input:
100 100 50 100 50 72 67 84 3 28 84 40 70 52 28 37 16 66 92 47 27 30 49 33 7 69 22 33 85 1 98 4 97 89 27 99 21 33 76 89 26 74 10 80 23 70 10 63 1 78 38 28 30 95 11 17 99 10 52 5 30 38 95 4 71 50 2 40 28 17 21 10 13 23 98 92 84 8 3 37 38 71 78 57 87 22 79 59 26 13 50 33 87 9 6 78 85 19 68 79 9 62 100 ...
output:
5 4 1 1 3 5 3 7 1 5 1 4 4 3 7 3 1 1 5 3 4 5 3 2 3 4 0 5 1 6 3 6 4 5 3 3 5 4 6 2 4 4 3 4 4 5 4 6 3 5
result:
ok 50 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
100 100 50 100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 100 91 65 31 33 13 98 45 91 54 50 94 66 78 5 28 13 100 4 15 63 55 2 72 49 97 18 57 59 40 ...
output:
25 1 14 45 3 27 26 14 3 47 46 22 20 1 6 1 22 27 15 39 25 36 35 24 14 12 35 32 48 5 9 2 26 4 27 17 36 35 10 15 38 7 16 2 48 3 31 32 48 6
result:
ok 50 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
100 100 50 100 99 99 99 97 97 97 95 95 95 93 93 93 91 91 91 89 89 89 87 87 87 85 85 85 83 83 83 81 81 81 79 79 79 77 77 77 75 75 75 73 73 73 71 71 71 69 69 69 67 67 67 68 68 70 70 70 72 72 72 74 74 74 76 76 76 78 78 78 80 80 80 82 82 82 84 84 84 86 86 86 88 88 88 90 90 90 92 92 92 94 94 94 96 96 96 ...
output:
9 6 23 6 1 21 5 18 5 15 2 3 16 3 15 26 2 3 12 1 1 0 20 27 26 3 3 3 30 22 30 1 1 0 26 11 13 13 16 21 2 12 7 22 7 13 2 9 8 15
result:
ok 50 lines
Test #7:
score: 0
Accepted
time: 1ms
memory: 6388kb
input:
100 100 50 100 99 99 99 97 97 97 95 95 95 93 93 93 91 91 91 89 89 89 87 87 87 85 85 85 83 83 83 81 81 81 79 79 79 77 77 77 75 75 75 73 73 73 71 71 71 69 69 69 67 67 67 68 68 70 70 70 72 72 72 74 74 74 76 76 76 78 78 78 80 80 80 82 82 82 84 84 84 86 86 86 88 88 88 90 90 90 92 92 92 94 94 94 96 96 96 ...
output:
9 20 22 8 30 3 22 11 2 8 10 5 1 26 10 20 19 21 1 6 17 2 6 9 13 9 20 25 24 1 25 19 4 14 15 23 10 19 19 3 2 3 9 24 9 10 17 10 7 14
result:
ok 50 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 6172kb
input:
100 30 50 30 29 29 29 27 27 27 25 25 25 23 23 23 21 21 21 19 19 19 17 17 17 15 15 15 13 13 13 11 11 11 9 9 9 7 7 7 5 5 5 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 4 4 4 6 6 6 8 8 8 10 10 10 12 12 12 14 14 14 16 16 16 18 18 18 20 20 20 22 22 22 24 24 24 26 26 26 28 28 28 30 29 60 12 67 26 10 71 29 70 5...
output:
9 15 10 3 14 21 20 17 4 8 18 0 2 6 16 3 11 12 7 14 2 8 17 3 13 7 3 3 7 21 6 6 10 2 9 11 5 0 18 9 20 14 2 2 7 26 3 3 9 13
result:
ok 50 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
10 10 50 10 7 7 4 1 9 3 8 1 10 8 9 2 7 7 6 4 2 7 4 5 8 6 7 10 2 1 9 7 2 9 1 2 7 5 8 6 9 1 3 5 2 9 5 5 3 5 8 4 8 7 5 10 7 3 7 6 1 9 1 2 8 3 1 9 7 4 1 6 9 10 7 3 9 5 4 3 1 8 2 2 3 5 10 4 6 10 5 6 4 5 8 10 7 2 6 5 8 1 6 6 4 2 6 6 8 10 8 7 9
output:
0 2 0 1 1 1 0 1 1 2 1 2 1 1 1 2 2 1 1 1 1 1 1 0 1 2 1 1 1 1 1 2 0 1 2 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1
result:
ok 50 lines
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #10:
score: 15
Accepted
time: 0ms
memory: 6056kb
input:
1000 1000 50 1000 922 228 50 969 778 800 874 487 278 681 989 234 951 889 87 926 534 311 876 955 989 810 841 423 580 204 360 127 808 441 249 754 777 831 192 797 272 163 832 471 669 837 129 774 425 435 315 515 626 725 883 415 932 9 891 34 146 288 321 980 972 776 449 458 188 75 412 81 523 705 137 564 7...
output:
10 5 8 4 6 3 5 3 5 5 3 5 7 6 6 6 10 5 2 5 9 4 10 6 7 7 10 4 5 5 2 7 7 7 6 6 5 7 5 6 10 6 9 2 3 9 6 6 5 7
result:
ok 50 lines
Test #11:
score: -15
Time Limit Exceeded
input:
100000 10 50 10 6 4 3 1 7 3 5 3 4 10 3 8 2 10 4 6 7 3 10 10 10 10 1 5 2 1 4 8 8 2 2 8 8 5 9 6 6 7 9 1 3 10 2 8 3 3 3 9 10 2 7 3 10 2 3 5 9 6 9 10 4 7 4 6 9 4 8 7 2 5 5 9 6 5 9 4 7 6 9 1 5 8 5 2 10 2 6 3 3 2 9 9 3 1 10 10 1 5 9 5 6 9 5 9 3 9 9 6 8 8 9 4 8 3 7 4 10 6 5 4 7 4 5 4 1 2 7 3 6 9 7 4 7 9 4 ...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #29:
score: 0
Time Limit Exceeded
input:
100000 14 100000 14 13 9 6 8 12 6 8 14 12 6 5 6 4 10 8 11 1 14 12 4 3 3 13 10 4 3 1 1 1 2 10 1 3 6 3 8 13 14 4 9 13 13 12 13 8 4 7 5 1 14 3 4 6 2 4 7 9 4 10 7 8 7 13 6 2 7 14 2 13 10 1 14 5 1 14 9 14 11 4 7 12 5 13 13 7 3 9 6 4 3 9 7 7 5 10 9 6 1 14 11 14 10 8 7 5 14 12 12 4 2 13 11 1 6 6 12 1 2 8 4...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%