oj.uz

Submission #620442

# Submission time Handle Problem Language Result Execution time Memory
620442 2022-08-03T06:03:39 Z 반딧불(#8518) Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 12280 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];

void makeEdges(){
    set<int> st;
    vector<pair<int, int> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(-arr[i], i));
    sort(vec.begin(), vec.end());
    for(int i=0; i<n; i++) vec[i].first = -vec[i].first;
    int s = 0;
    for(int d=k; d>=1; d--){
        int e = s;
        while(e<n && vec[e].first == d) e++;
        if(s==e) continue;
        for(int i=s; i<e; i++) st.insert(vec[i].second);
        for(int i=s; i<e; i++){
            int x = vec[i].second;
            auto it = st.lower_bound(x);
            if(it != st.begin()){
                link[x].push_back(*prev(it));
                link[*prev(it)].push_back(x);
            }
            if(next(it) != st.end()){
                link[x].push_back(*next(it));
                link[*next(it)].push_back(x);
            }
        }
        s=e;
    }
}

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]);
    makeEdges();
    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:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:61:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2644 KB Output is correct
2 Correct 148 ms 12192 KB Output is correct
3 Correct 133 ms 12220 KB Output is correct
4 Correct 157 ms 12260 KB Output is correct
5 Correct 155 ms 12280 KB Output is correct
6 Correct 212 ms 12260 KB Output is correct
7 Correct 273 ms 12244 KB Output is correct
8 Correct 106 ms 11628 KB Output is correct
9 Correct 129 ms 12108 KB Output is correct
10 Correct 106 ms 11900 KB Output is correct
11 Correct 184 ms 12060 KB Output is correct
12 Correct 226 ms 12128 KB Output is correct
13 Correct 181 ms 12144 KB Output is correct
14 Correct 204 ms 12092 KB Output is correct
15 Correct 204 ms 12048 KB Output is correct
16 Correct 171 ms 12048 KB Output is correct
17 Correct 169 ms 12276 KB Output is correct
18 Correct 155 ms 12256 KB Output is correct
19 Correct 169 ms 12280 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 12268 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 2078 ms 12260 KB Time limit exceeded
2 Halted 0 ms 0 KB -