제출 #24684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24684		Ushio	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	56 ms	30044 KiB

railway_trip

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

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<int> leftEq(n, -1), leftLt(n, -1);
    Vector<int> rightEq(n, -1), rightLt(n, -1);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        while (!stk.empty() && A[i] >= A[stk.back()]) {
            leftEq[i] = stk.back();
            if (A[i] > A[stk.back()]) {
                leftLt[i] = stk.back();
            }
            stk.pop_back();
        }
        stk.push_back(i);
    }
    stk.clear();
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && A[i] >= A[stk.back()]) {
            rightEq[i] = stk.back();
            if (A[i] > A[stk.back()]) {
                rightLt[i] = stk.back();
            }
            stk.pop_back();
        }
        stk.push_back(i);
    }
    Vector<int> leftSon(n, -1), rightSon(n, -1);
    Vector<int> parent(n, -1);
    Vector<int> skip(n, -1);
    Vector<int> level(n, 0);
    queue<pair<int, int>> qu;
    qu.push(make_pair(1, 0));
    while (!qu.empty()) {
        int sonType = qu.front().first;
        int node = qu.front().second;
        qu.pop();
        if (sonType == 0) {
            leftSon[node] = leftEq[node];
            rightSon[node] = rightLt[node];
        } else {
            leftSon[node] = leftLt[node];
            rightSon[node] = rightEq[node];
        }
        if (leftSon[node] != -1) {
            qu.push(make_pair(0, leftSon[node]));
            parent[leftSon[node]] = node;
            level[leftSon[node]] = level[node] + 1;
        }
        if (rightSon[node] != -1) {
            qu.push(make_pair(1, rightSon[node]));
            parent[rightSon[node]] = node;
            level[rightSon[node]] = level[node] + 1;
        }
    }
    for (int node = 0; node < n; ++node) {
        for (int des = leftSon[node]; des != -1; des = rightSon[des]) {
            if (des != leftSon[node] &&
                    (rightSon[des] == -1 || A[des] > A[rightSon[des]])) {
                skip[des] = node;
            }
        }
        for (int des = rightSon[node]; des != -1; des = leftSon[des]) {
            if (des != rightSon[node] &&
                    (leftSon[des] == -1 || A[des] > A[leftSon[des]])) {
                skip[des] = node;
            }
        }
    }
    const int LOG = 20;
    array<Vector<int>, LOG> anc;
    fill(anc.begin(), anc.end(), Vector<int>(n));
    parent[0] = 0;
    for (int node = 0; node < n; ++node) {
        anc[0][node] = parent[node];
    }
    for (int k = 1; k < LOG; ++k) {
        for (int node = 0; node < n; ++node) {
            anc[k][node] = anc[k - 1][anc[k - 1][node]];
        }
    }
    array<Vector<int>, LOG> skipAnc;
    array<Vector<int>, LOG> skipCost;
    fill(skipAnc.begin(), skipAnc.end(), Vector<int>(n));
    fill(skipCost.begin(), skipCost.end(), Vector<int>(n));
    for (int node = 0; node < n; ++node) {
        if (skip[node] == -1) {
            skip[node] = parent[node];
        }
        skipAnc[0][node] = skip[node];
        skipCost[0][node] = (skip[node] != node);
    }
    for (int k = 1; k < LOG; ++k) {
        for (int node = 0; node < n; ++node) {
            skipAnc[k][node] = skipAnc[k - 1][skipAnc[k - 1][node]];
            skipCost[k][node] = skipCost[k - 1][node]
                + skipCost[k - 1][skipAnc[k - 1][node]];
        }
    }
    auto goUp = [&](int node, int lvl) -> int {
        for (int k = 0; k < LOG; ++k) {
            if (lvl & (1 << k)) {
                node = anc[k][node];
            }
        }
        return node;
    };
    auto lca = [&](int x, int y) -> int {
        if (level[y] > level[x]) {
            y = goUp(y, level[y] - level[x]);
        } else if (level[x] > level[y]) {
            x = goUp(x, level[x] - level[y]);
        }
        if (x == y) {
            return x;
        }
        for (int k = LOG - 1; k >= 0; --k) {
            if (anc[k][x] != anc[k][y]) {
                x = anc[k][x];
                y = anc[k][y];
            }
        }
        return parent[x];
    };
    while (q-- > 0) {
        int x, y;
        cin >> x >> y;
        x--; y--;


        int l = lca(x, y);
        int ans = 0;
        for (int k = LOG - 1; k >= 0; --k) {
            if (level[skipAnc[k][x]] >= level[l]) {
                ans += skipCost[k][x];
                x = skipAnc[k][x];
            }
            if (level[skipAnc[k][y]] >= level[l]) {
                ans += skipCost[k][y];
                y = skipAnc[k][y];
            }
        }
        int ans1 = ans + level[x] + level[y] - 2 * level[l];
        int v1 = skip[x];
        int v2 = skip[y];
        if (level[v1] > level[v2]) {
            swap(v1, v2);
            swap(x, y);
        }
        int ans2 = ans + 1 + level[x] - level[v2];
        int ans3 = ans + 2;
        for (int k = LOG - 1; k >= 0; --k) {
            if (level[skipAnc[k][v2]] >= level[v1]) {
                ans3 += skipCost[k][v2];
                v2 = skipAnc[k][v2];
            }
        }
        ans3 += level[v2] - level[v1];
        ans = min({ans1, ans2, ans3});
        cout << ans - 1 << '\n';
    }
}

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