oj.uz

답안 #21586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
21586 2017-04-14T15:18:24 Z Ushio Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 33944 KB 
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

const int INF = 0x3f3f3f3f;

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<Vector<int>> graph(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        int prev = -1;
        while (!stk.empty() && A[i] > A[stk.back()]) {
            if (A[stk.back()] > prev) {
                graph[i].push_back(stk.back());
                graph[stk.back()].push_back(i);
            }
            prev = A[stk.back()];
            stk.pop_back();
        }
        if (!stk.empty()) {
            graph[i].push_back(stk.back());
            graph[stk.back()].push_back(i);
        }
        stk.push_back(i);
    }
    if (k <= 20 && q > 50) {
        Vector<Vector<int>> dists(k + 1, Vector<int>(n, INF));
        Vector<Vector<int>> n1(k + 1, Vector<int>(n, -1));
        Vector<Vector<int>> n2(k + 1, Vector<int>(n, -1));
        for (int j = k; j >= 1; --j) {
            queue<pair<int, int>> q;
            for (int i = 0; i < n; ++i) {
                if (A[i] == j) {
                    dists[j][i] = 0;
                    n1[j][i] = i;
                    q.push(make_pair(i, i));
                }
            }
            while (!q.empty()) {
                int node = q.front().first;
                int start = q.front().second;
                q.pop();

                for (int to: graph[node]) {
                    if (dists[j][to] >= dists[j][node] + 1) {
                        dists[j][to] = dists[j][node] + 1;
                        if (start > to) {
                            n2[j][to] = start;
                        } else {
                            n1[j][to] = start;
                        }
                        q.push(make_pair(to, start));
                    }
                }
            }
        }
        Vector<int> log2(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            log2[i] = log2[i / 2] + 1;
        }
        int clog2 = log2[n];
        Vector<Vector<int>> rmq(clog2 + 1, Vector<int>(n));
        for (int i = 0; i < n; ++i) {
            rmq[0][i] = A[i];
        }
        for (int j = 1; j <= clog2; ++j) {
            int y = 1 << j - 1;
            for (int i = 0; i + (1 << j) <= n; ++i) {
                rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + y]);
            }
        }
        auto getMax = [&](int left, int right) -> int {
            if (right < left) {
                return -INF;
            }
            int d = log2[right - left + 1];
            return max(rmq[d][left], rmq[d][right - (1 << d) + 1]);
        };
        Vector<int> valCnt(k + 1, 0);
        Vector<int> posInVal(n);
        for (int i = 0; i < n; ++i) {
            posInVal[i] = valCnt[A[i]]++;
        }

        while (q-- > 0) {
            int from, to;
            cin >> from >> to;
            from--; to--;
            int h = max(A[from], A[to]);
            int ans = INF;
            for (int i = h; i <= k; ++i) {
                for (int x1: {n1[i][from], n2[i][from]}) {
                    for (int x2: {n1[i][to], n2[i][to]}) {
                        int p1 = min(x1, x2);
                        int p2 = max(x1, x2);
                        if (x1 != -1 && x2 != -1 &&
                                getMax(p1 + 1, p2 - 1) <= A[x1]) {
                            int cost = dists[i][from] + dists[i][to];
                            cost += posInVal[p2] - posInVal[p1] - 1;
                            ans = min(ans, cost);
                        }
                    }
                }
            }
            cout << ans << '\n';
        }
    } else {
        while (q-- > 0) {
            int s, d;
            cin >> s >> d;
            s--; d--;
            Vector<int> dist(n, -1);
            dist[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty() && dist[d] == -1) {
                int node = q.front();
                q.pop();
                for (int to: graph[node]) {
                    if (dist[to] == -1) {
                        dist[to] = dist[node] + 1;
                        q.push(to);
                    }
                }
            }
            cout << dist[d] - 1 << '\n';
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2188 KB Output is correct
2 Correct 136 ms 8900 KB Output is correct
3 Correct 133 ms 8976 KB Output is correct
4 Correct 146 ms 9048 KB Output is correct
5 Correct 136 ms 9080 KB Output is correct
6 Correct 146 ms 9124 KB Output is correct
7 Correct 133 ms 9144 KB Output is correct
8 Correct 49 ms 8988 KB Output is correct
9 Correct 56 ms 8732 KB Output is correct
10 Correct 46 ms 8988 KB Output is correct
11 Correct 116 ms 8884 KB Output is correct
12 Correct 119 ms 8888 KB Output is correct
13 Correct 113 ms 8888 KB Output is correct
14 Correct 123 ms 8884 KB Output is correct
15 Correct 123 ms 8888 KB Output is correct
16 Correct 109 ms 8888 KB Output is correct
17 Correct 136 ms 9144 KB Output is correct
18 Correct 126 ms 9144 KB Output is correct
19 Correct 76 ms 9144 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 9144 KB Execution timed out
2 Halted 0 ms 0 KB -