oj.uz

Submission #896566

# Submission time Handle Problem Language Result Execution time Memory
896566 2024-01-01T16:57:41 Z Aiperiii Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 10876 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    int n,k,qu;
    cin>>n>>k>>qu;
    vector <int> l(n);
    for(int i=0;i<n;i++)cin>>l[i];
    vector <int> g[n];
    for(int i=0;i<n;i++){
        int mx=0;
        for(int j=i+1;j<n;j++){
            if(l[j]>mx){
                mx=l[j];
                g[i].pb(j);
                g[j].pb(i);
            }
            if(mx>=l[i])break;
        }
    }
    while(qu--){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        queue <int> q;
        vector <int> d(n,1e18);
        q.push(a);
        d[a]=0;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            for(auto to : g[v]){
                if(d[to]>d[v]+1){
                    d[to]=d[v]+1;
                    q.push(to);
                }
            }
        }
        int x=d[b]-1;
        cout<<x<<"\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 128 ms 9164 KB Output is correct
3 Correct 127 ms 9420 KB Output is correct
4 Correct 124 ms 9552 KB Output is correct
5 Correct 123 ms 9556 KB Output is correct
6 Correct 149 ms 9656 KB Output is correct
7 Correct 158 ms 10016 KB Output is correct
8 Correct 43 ms 7280 KB Output is correct
9 Correct 1894 ms 8160 KB Output is correct
10 Correct 1571 ms 8428 KB Output is correct
11 Correct 599 ms 8896 KB Output is correct
12 Correct 850 ms 8976 KB Output is correct
13 Correct 989 ms 9040 KB Output is correct
14 Correct 806 ms 9028 KB Output is correct
15 Correct 929 ms 9312 KB Output is correct
16 Correct 777 ms 9148 KB Output is correct
17 Correct 147 ms 10608 KB Output is correct
18 Correct 141 ms 10616 KB Output is correct
19 Correct 96 ms 10876 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 9428 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 2036 ms 9816 KB Time limit exceeded
2 Halted 0 ms 0 KB -