oj.uz

Submission #801957

# Submission time Handle Problem Language Result Execution time Memory
801957 2023-08-02T08:42:02 Z vjudge1 Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 13960 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int INF = 1e9 + 10;

vector<int> g[N];
int n, k, q;
int H[N];

vector<int> dist(N);
vector<int> pr(N);

int LIM = INF;

void bfs(vector<int> st) {
    dist.assign(n + 1, INF);
    pr.assign(n + 1, -1);
    queue<int> q;
    vector<bool> vis(n + 1, false);
    int inx = 0;
    for(int c : st) {
        dist[c] = 0;
        vis[c] = 1;
        pr[c] = inx++;
        q.push(c);
    } 
    while(!q.empty()) {
        int s = q.front();
        q.pop();
        for(int to : g[s]) {
            if(vis[to] || H[to] > LIM) continue;
            pr[to] = pr[s];
            dist[to] = dist[s] + 1;
            vis[to] = 1;
            q.push(to); 
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) 
        cin >> H[i];
    vector<int> st;
    for(int i = 1; i <= n; i++) {
        while(!st.empty() && H[st.back()] < H[i]) {
            g[i].push_back(st.back());
            st.pop_back();
        }
        if(!st.empty()) {
            g[i].push_back(st.back());
            if(H[st.back()] == H[i]) st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for(int i = n; i >= 1; i--) {
        while(!st.empty() && H[st.back()] < H[i]) {
            g[i].push_back(st.back());
            st.pop_back();
        }
        if(!st.empty()) {
            g[i].push_back(st.back());
            if(H[st.back()] == H[i]) st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    if(q <= 50) {
        while(q--) {
            int u, v;
            cin >> u >> v;
            bfs({u});
            cout << dist[v] - 1 << '\n';
        }
        return 0;
    }
    vector<int> t[k + 1];
    for(int i = 1; i <= n; i++) 
        t[H[i]].push_back(i);
    vector<int> res(q, INF);
    vector<pair<pair<int, int>, int>> qr;
    for(int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        qr.push_back({{u, v}, i});
    }
    for(int i = k; i >= 1; i--) {
        LIM = i;
        bfs(t[i]);
        for(auto c : qr) {
            int u = c.first.first, v = c.first.second, ix = c.second;
            res[ix] = min(res[ix], dist[u] + dist[v] + abs(pr[u] - pr[v]));
        }
    }
    for(int i = 0; i < q; i++) 
        cout << res[i] - 1 << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 134 ms 7932 KB Output is correct
3 Correct 156 ms 8064 KB Output is correct
4 Correct 154 ms 8196 KB Output is correct
5 Correct 159 ms 8232 KB Output is correct
6 Correct 164 ms 8276 KB Output is correct
7 Correct 162 ms 8380 KB Output is correct
8 Correct 45 ms 6996 KB Output is correct
9 Correct 49 ms 7060 KB Output is correct
10 Correct 47 ms 7040 KB Output is correct
11 Correct 120 ms 7456 KB Output is correct
12 Correct 122 ms 7380 KB Output is correct
13 Correct 126 ms 7456 KB Output is correct
14 Correct 124 ms 7452 KB Output is correct
15 Correct 123 ms 7460 KB Output is correct
16 Correct 120 ms 7460 KB Output is correct
17 Correct 167 ms 8268 KB Output is correct
18 Correct 186 ms 8372 KB Output is correct
19 Correct 89 ms 7844 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 10636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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