Submission #21581

#	Time	Username	Problem	Language	Result	Execution time	Memory
21581		Ushio	Railway Trip (JOI17_railway_trip)	C++14	5 / 100	2000 ms	46448 KiB

railway_trip

#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k, q;
    cin >> n >> k >> q;

    vector<int> A(n);
    vector<int> stk;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        int prev = -1;
        while (!stk.empty() && A[i] > A[stk.back()]) {
            if (A[stk.back()] > prev) {
                graph[i].push_back(stk.back());
                graph[stk.back()].push_back(i);
            }
            prev = A[stk.back()];
            stk.pop_back();
        }
        if (!stk.empty()) {
            graph[i].push_back(stk.back());
            graph[stk.back()].push_back(i);
        }
        stk.push_back(i);
    }
    if (k <= 20) {
        vector<vector<int>> dists(n, vector<int>(k + 1, INF));
        vector<vector<int>> n1(n, vector<int>(k + 1, -1));
        vector<vector<int>> n2(n, vector<int>(k + 1, -1));
        for (int i = 0; i < n; ++i) {
            n1[i][A[i]] = i;
            dists[i][A[i]] = 0;
            queue<pair<int, int>> q;
            q.push(make_pair(i, 0));
            while (!q.empty()) {
                int node = q.front().first;
                int cost = q.front().second;
                q.pop();
                for (int to: graph[node]) {
                    if (A[to] > A[node] && dists[i][A[to]] >= cost + 1) {
                        dists[i][A[to]] = cost + 1;
                        q.push(make_pair(to, cost + 1));
                        if (n1[i][A[to]] == -1) {
                            n1[i][A[to]] = to;
                        } else {
                            n2[i][A[to]] = to;
                        }
                    }
                }
            }
        }
        vector<int> log2(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            log2[i] = log2[i / 2] + 1;
        }
        int clog2 = log2[n];
        vector<vector<int>> rmq(clog2 + 1, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            rmq[0][i] = A[i];
        }
        for (int j = 1; j <= clog2; ++j) {
            int y = 1 << j - 1;
            for (int i = 0; i + (1 << j) <= n; ++i) {
                rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + y]);
            }
        }
        auto getMax = [&](int left, int right) -> int {
            if (right < left) {
                return -INF;
            }
            int d = log2[right - left + 1];
            return max(rmq[d][left], rmq[d][right - (1 << d) + 1]);
        };
        vector<int> valCnt(k + 1, 0);
        vector<int> posInVal(n);
        for (int i = 0; i < n; ++i) {
            posInVal[i] = valCnt[A[i]]++;
        }

        while (q-- > 0) {
            int from, to;
            cin >> from >> to;
            from--; to--;
            int h = max(A[from], A[to]);
            int ans = INF;
            if (from == 3 && to == 8) {
                cerr << dists[3][2] << endl;
            }
            for (int i = h; i <= k; ++i) {
                for (int x1: {n1[from][i], n2[from][i]}) {
                    for (int x2: {n1[to][i], n2[to][i]}) {
                        int p1 = min(x1, x2);
                        int p2 = max(x1, x2);
                        if (x1 != -1 && x2 != -1 &&
                                getMax(p1 + 1, p2 - 1) <= A[x1]) {
                            int cost = dists[from][i] + dists[to][i];
                            cost += posInVal[p2] - posInVal[p1] - 1;
                            ans = min(ans, cost);
                        }
                    }
                }
            }
            cout << ans << '\n';
        }
    } else {
        while (q-- > 0) {
            int s, d;
            cin >> s >> d;
            s--; d--;
            vector<int> dist(n, -1);
            dist[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty() && dist[d] == -1) {
                int node = q.front();
                q.pop();
                for (int to: graph[node]) {
                    if (dist[to] == -1) {
                        dist[to] = dist[node] + 1;
                        q.push(to);
                    }
                }
            }
            cout << dist[d] - 1 << '\n';
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55