답안 #24767 :: oj.uz

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

#	결과	메모리	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	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

#	결과	실행 시간	메모리	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

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

답안 #24767

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