답안 #24766 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24766	2017-06-13T10:40:15 Z	Ushio	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	139 ms	115636 KB

railway_trip

#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);
    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	2332 KB	Output is correct
2	Correct	2332 KB	Output is correct
3	Correct	2332 KB	Output is correct
4	Correct	2332 KB	Output is correct
5	Correct	2200 KB	Output is correct
6	Correct	2200 KB	Output is correct
7	Correct	2200 KB	Output is correct
8	Correct	2200 KB	Output is correct
9	Correct	2200 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3348 KB	Output is correct
2	Correct	109 ms	99904 KB	Output is correct
3	Correct	119 ms	105964 KB	Output is correct
4	Correct	129 ms	110640 KB	Output is correct
5	Correct	109 ms	112632 KB	Output is correct
6	Correct	126 ms	115032 KB	Output is correct
7	Correct	133 ms	115412 KB	Output is correct
8	Correct	83 ms	59856 KB	Output is correct
9	Correct	119 ms	90424 KB	Output is correct
10	Correct	86 ms	76728 KB	Output is correct
11	Correct	123 ms	88228 KB	Output is correct
12	Correct	126 ms	88388 KB	Output is correct
13	Correct	106 ms	88208 KB	Output is correct
14	Correct	136 ms	88216 KB	Output is correct
15	Correct	139 ms	88372 KB	Output is correct
16	Correct	129 ms	88404 KB	Output is correct
17	Correct	133 ms	115416 KB	Output is correct
18	Correct	106 ms	115416 KB	Output is correct
19	Correct	119 ms	115636 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	129 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	126 ms	115412 KB	Execution killed because of forbidden syscall writev (20)
2	Halted	0 ms	0 KB	-

답안 #24766

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 25.0

Subtask #4 0 / 55.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 25.0

Subtask #4
0 / 55.0