oj.uz

Submission #24767

# Submission time Handle Problem Language Result Execution time Memory
24767 2017-06-13T10:44:55 Z Ushio Railway Trip (JOI17_railway_trip) C++14
20 / 100
 176 ms 114060 KB 
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

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);
    tree.reserve(2 * 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3308 KB Output is correct
2 Correct 126 ms 98416 KB Output is correct
3 Correct 109 ms 104576 KB Output is correct
4 Correct 133 ms 109148 KB Output is correct
5 Correct 129 ms 111160 KB Output is correct
6 Correct 123 ms 113508 KB Output is correct
7 Correct 133 ms 113852 KB Output is correct
8 Correct 69 ms 61352 KB Output is correct
9 Correct 106 ms 88376 KB Output is correct
10 Correct 113 ms 77616 KB Output is correct
11 Correct 116 ms 86504 KB Output is correct
12 Correct 109 ms 86528 KB Output is correct
13 Correct 129 ms 86376 KB Output is correct
14 Correct 96 ms 86360 KB Output is correct
15 Correct 96 ms 86540 KB Output is correct
16 Correct 116 ms 86532 KB Output is correct
17 Correct 176 ms 113852 KB Output is correct
18 Correct 126 ms 113852 KB Output is correct
19 Correct 129 ms 114060 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 101716 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 113852 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -