Submission #24682

# Submission time Handle Problem Language Result Execution time Memory
24682 2017-06-11T16:16:09 Z Ushio Railway Trip (JOI17_railway_trip) C++14
0 / 100
33 ms 30044 KB
#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]) {
                skip[des] = node;
            }
        }
        for (int des = rightSon[node]; des != -1; des = leftSon[des]) {
            if (des != rightSon[node]) {
                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 + 3;
        ans = min({ans1, ans2, ans3});
        cout << ans - 1 << '\n';
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2188 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2452 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 29996 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 30044 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -