oj.uz

답안 #24764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24764 2017-06-13T10:37:22 Z Ushio Railway Trip (JOI17_railway_trip) C++14
20 / 100
 143 ms 115632 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);
    }
};

class SegmentTree {
public:
    SegmentTree() = default;
    SegmentTree(const vector<int>& a):
        tree(vector<pair<int, int>>(4 * SZ(a) + 5)), n(SZ(a)) {
            build(0, 0, n - 1, a);
        }

    pair<int, int> query(int left, int right) const {
        pair<int, int> ret = query(0, 0, n - 1, left, right);
        ret.second = -ret.second;
        return ret;
    }
private:
    vector<pair<int, int>> tree;
    int n;

    void build(int node, int left, int right, const vector<int>& a) {
        if (left == right) {
            tree[node] = make_pair(a[left], -left);
        } else {
            int mid = (left + right) / 2;
            build(2 * node + 1, left, mid, a);
            build(2 * node + 2, mid + 1, right, a);
            tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    pair<int, int> query(int node, int left, int right, int lq, int rq) const {
        if (lq <= left && right <= rq) {
            return tree[node];
        } else {
            int mid = (left + right) / 2;
            pair<int, int> ret(-1, -1);
            if (lq <= mid) {
                ret = query(2 * node + 1, left, mid, lq, rq);
            }
            if (rq > mid) {
                ret = max(ret, query(2 * node + 2, mid + 1, right, lq, rq));
            }
            return ret;
        }
    }
};

vector<vector<int>> tree;
vector<int> indexToNode;
SegmentTree t;

const int LOG = 21;
array<vector<int>, LOG> anc;
array<vector<int>, LOG> ancCost;
vector<int> depth;
vector<int> posInParent;

int build(const vector<int>& a, int left, int right) {
    tree.push_back(vector<int>());
    int index = SZ(tree) - 1;
    if (left + 1 == right) {
        indexToNode[left] = index;
    } else {
        pair<int, int> imax = t.query(left + 1, right - 1);
        vector<int> poss = {left, imax.second};
        while (imax.second + 1 < right) {
            pair<int, int> cmax = t.query(imax.second + 1, right - 1);
            if (cmax.first != imax.first) {
                break;
            }
            poss.push_back(cmax.second);
            imax = cmax;
        }
        poss.push_back(right);
        for (int i = 0; i < SZ(poss) - 1; ++i) {
            int x = build(a, poss[i], poss[i + 1]);
            tree[index].push_back(x);
        }
    }
    return index;
}

void assignParent(int son, int parent, int costLeft, int costRight) {
    costLeft = min(costLeft, costRight + 1);
    costRight = min(costRight, costLeft + 1);
    if (costLeft == costRight + 1) {
        anc[0][son] = 3 * parent;
        ancCost[0][son] = costRight;
    } else if (costLeft == costRight) {
        anc[0][son] = 3 * parent + 1;
        ancCost[0][son] = costRight;
    } else {
        anc[0][son] = 3 * parent + 2;
        ancCost[0][son] = costLeft;
    }
}

void genDistTrees(int node) {
    for (int i = 0; i < SZ(tree[node]); ++i) {
        int to = tree[node][i];
        int costLeft = i;
        int costRight = SZ(tree[node]) - i - 1;
        posInParent[to] = i;
        depth[to] = depth[node] + 1;
        assignParent(3 * to, node, costLeft + 1, costRight);
        assignParent(3 * to + 1, node, costLeft, costRight);
        assignParent(3 * to + 2, node, costLeft, costRight + 1);
        genDistTrees(to);
    }
}

pair<int, int> ascend(int node, int height) {
    int cost = 0;
    for (int k = 0; k < LOG; ++k) {
        if (height & (1 << k)) {
            cost += ancCost[k][node];
            node = anc[k][node];
        }
    }
    return make_pair(node, cost);
}

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);
    int rootCycle = true;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i != 0 && i != n - 1 && a[i] == k) {
            rootCycle = false;
        }
    }
    t = SegmentTree(a);
    indexToNode = vector<int>(n);
    int root = build(a, 0, n - 1);
    for (int i = 0; i < LOG; ++i) {
        anc[i] = vector<int>(3 * SZ(tree));
        ancCost[i] = vector<int>(3 * SZ(tree));
    }
    for (int i = 0; i < 3; ++i) {
        anc[i][root + i] = root;
        ancCost[i][root + i] = 0;
    }
    depth = vector<int>(SZ(tree), 0);
    posInParent = vector<int>(SZ(tree), -1);
    genDistTrees(root);
    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i < SZ(anc[k]); ++i) {
            anc[k][i] = anc[k - 1][anc[k - 1][i]];
            ancCost[k][i] = ancCost[k - 1][i] + 
                ancCost[k - 1][anc[k - 1][i]];
        }
    }

    while (q-- > 0) {
        int a, b;
        cin >> a >> b;
        if (a + 1 == b) {
            cout << "0\n";
            continue;
        }
        a--; b--;
        if (a > b) {
            swap(a, b);
        }
        a = indexToNode[a] * 3 + 2;
        b = indexToNode[b - 1] * 3;
        int add = 0;
        if (depth[b / 3] > depth[a / 3]) {
            pair<int, int> c = ascend(b, depth[b / 3] - depth[a / 3]);
            b = c.first;
            add += c.second;
        } else if (depth[a / 3] > depth[b / 3]) {
            pair<int, int> c = ascend(a, depth[a / 3] - depth[b / 3]);
            a = c.first;
            add += c.second;
        }
        for (int k = LOG - 1; k >= 0; --k) {
            if (anc[k][a] / 3 != anc[k][b] / 3) {
                add += ancCost[k][a] + ancCost[k][b];
                a = anc[k][a];
                b = anc[k][b];
            }
        }
        int ans = add + posInParent[b / 3] - posInParent[a / 3] - 1
            + (a % 3 == 2) + (b % 3 == 0);
        if (anc[0][a] / 3 != root || rootCycle) {
            ans = min(ans, add + posInParent[a / 3] +
                    (SZ(tree[anc[0][a] / 3]) - posInParent[b / 3] - 1) +
                    (a % 3 == 0) + (b % 3 == 2) + 1);
        }
        cout << ans - 1 << '\n';
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 0 ms 2332 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2332 KB Output is correct
5 Correct 0 ms 2200 KB Output is correct
6 Correct 0 ms 2200 KB Output is correct
7 Correct 0 ms 2200 KB Output is correct
8 Correct 0 ms 2200 KB Output is correct
9 Correct 0 ms 2200 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3348 KB Output is correct
2 Correct 96 ms 99904 KB Output is correct
3 Correct 113 ms 105964 KB Output is correct
4 Correct 99 ms 110640 KB Output is correct
5 Correct 126 ms 112632 KB Output is correct
6 Correct 143 ms 115032 KB Output is correct
7 Correct 139 ms 115412 KB Output is correct
8 Correct 69 ms 59856 KB Output is correct
9 Correct 99 ms 90416 KB Output is correct
10 Correct 99 ms 76732 KB Output is correct
11 Correct 99 ms 88224 KB Output is correct
12 Correct 106 ms 88384 KB Output is correct
13 Correct 83 ms 88208 KB Output is correct
14 Correct 96 ms 88212 KB Output is correct
15 Correct 109 ms 88372 KB Output is correct
16 Correct 136 ms 88408 KB Output is correct
17 Correct 119 ms 115416 KB Output is correct
18 Correct 143 ms 115416 KB Output is correct
19 Correct 136 ms 115632 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 139 ms 103128 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 123 ms 115412 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -