Submission #21586

#	Time	Username	Problem	Language	Result	Execution time	Memory
21586		Ushio	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2000 ms	33944 KiB

railway_trip

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

const int INF = 0x3f3f3f3f;

template<class T>
class Vector: public vector<T> {
public:
    Vector(): vector<T>() {}
    Vector(int n): vector<T>(n) {}
    Vector(int n, const T& e): vector<T>(n, e){}
    T& operator[](size_t pos) {
        assert(0 <= pos && pos < vector<T>::size());
        return vector<T>::operator[](pos);
    }
    const T& operator[](size_t pos) const {
        assert(0 <= pos && pos < vector<T>::size());
        return vector<T>::operator[](pos);
    }
};

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 && q > 50) {
        Vector<Vector<int>> dists(k + 1, Vector<int>(n, INF));
        Vector<Vector<int>> n1(k + 1, Vector<int>(n, -1));
        Vector<Vector<int>> n2(k + 1, Vector<int>(n, -1));
        for (int j = k; j >= 1; --j) {
            queue<pair<int, int>> q;
            for (int i = 0; i < n; ++i) {
                if (A[i] == j) {
                    dists[j][i] = 0;
                    n1[j][i] = i;
                    q.push(make_pair(i, i));
                }
            }
            while (!q.empty()) {
                int node = q.front().first;
                int start = q.front().second;
                q.pop();

                for (int to: graph[node]) {
                    if (dists[j][to] >= dists[j][node] + 1) {
                        dists[j][to] = dists[j][node] + 1;
                        if (start > to) {
                            n2[j][to] = start;
                        } else {
                            n1[j][to] = start;
                        }
                        q.push(make_pair(to, start));
                    }
                }
            }
        }
        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;
            for (int i = h; i <= k; ++i) {
                for (int x1: {n1[i][from], n2[i][from]}) {
                    for (int x2: {n1[i][to], n2[i][to]}) {
                        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[i][from] + dists[i][to];
                            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: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55