oj.uz

Submission #801953

# Submission time Handle Problem Language Result Execution time Memory
801953 2023-08-02T08:40:30 Z vjudge1 Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 13992 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);

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]) 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});
            // for(int i = 1; i <= n; i++)     
            //     cout << dist[i] << ' ';
            // cout << '\n';
            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--) {
        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 3476 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 3432 KB Output is correct
2 Correct 147 ms 8140 KB Output is correct
3 Correct 144 ms 8340 KB Output is correct
4 Correct 149 ms 8468 KB Output is correct
5 Correct 173 ms 8528 KB Output is correct
6 Correct 162 ms 8652 KB Output is correct
7 Correct 167 ms 8852 KB Output is correct
8 Correct 46 ms 7200 KB Output is correct
9 Correct 52 ms 7652 KB Output is correct
10 Correct 59 ms 7380 KB Output is correct
11 Correct 128 ms 8040 KB Output is correct
12 Correct 120 ms 8056 KB Output is correct
13 Correct 119 ms 8020 KB Output is correct
14 Correct 119 ms 8032 KB Output is correct
15 Correct 133 ms 8048 KB Output is correct
16 Correct 121 ms 8020 KB Output is correct
17 Correct 173 ms 8964 KB Output is correct
18 Correct 165 ms 8972 KB Output is correct
19 Correct 86 ms 8408 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 10656 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 2059 ms 13992 KB Time limit exceeded
2 Halted 0 ms 0 KB -