oj.uz

Submission #620338

# Submission time Handle Problem Language Result Execution time Memory
620338 2022-08-03T04:56:15 Z 반딧불(#8518) Railway Trip (JOI17_railway_trip) C++17
5 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k, q;
int arr[100002];
vector<int> link[100002];
bool visited[100002];

int bfs(int s, int e){
    queue<pair<int, int> > que;
    fill(visited+1, visited+n+1, 0);
    que.push(make_pair(s, 0));
    visited[s] = 1;
    while(!que.empty()){
        pair<int, int> tmp = que.front(); que.pop();
        int x = tmp.first;
        if(x == e) return tmp.second;
        for(auto y: link[x]){
            if(!visited[y]){
                visited[y] = 1;
                que.push(make_pair(y, tmp.second+1));
            }
        }
    }
    exit(1);
}

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int g=1; g<=k; g++){
        vector<int> vec;
        for(int i=1; i<=n; i++) if(arr[i] >= g) vec.push_back(i);
        for(int i=0; i+1<(int)vec.size(); i++){
            link[vec[i]].push_back(vec[i+1]);
            link[vec[i+1]].push_back(vec[i]);
        }
    }
    while(q--){
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%d\n", bfs(s, e)-1);
    }
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:33:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d %d", &s, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9040 KB Output is correct
2 Correct 164 ms 12844 KB Output is correct
3 Correct 267 ms 20076 KB Output is correct
4 Correct 461 ms 41088 KB Output is correct
5 Correct 704 ms 75948 KB Output is correct
6 Runtime error 1356 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 15296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 1561 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -