oj.uz

Submission #780291

# Submission time Handle Problem Language Result Execution time Memory
780291 2023-07-12T07:58:45 Z 이동현(#10007) Railway Trip (JOI17_railway_trip) C++17
5 / 100
 2000 ms 30772 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Data{
    int pr, l, r, add;
    Data(){}
    Data(int pr, int l, int r, int add):pr(pr), l(l), r(r), add(add){}
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n + 2);
    a[0] = a[n + 1] = k + 1;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    n += 2;

    vector<Data> tr;
    tr.push_back(Data(-1, -1, -1, 0));
    vector<int> st(n);
    auto gen = [&](auto&&self, int x, int s, int e)->void{
        // cout << x << ' ' << s << ' ' << e << endl;
        if(s + 1 >= e){
            st[s] = x;
            return;
        }
        int mx = -1;

        for(int i = s + 1; i < e; ++i){
            mx = max(mx, a[i]);
        }
        int lst = s;
        vector<int> id;
        for(int i = s + 1; i < e; ++i){
            if(a[i] == mx){
                id.push_back((int)tr.size());
                tr.push_back(Data((lst == s ? x : -1), -1, -1, 0));
                self(self, id.back(), lst, i);
                lst = i;
            }
        }
        id.push_back((int)tr.size());
        tr.push_back(Data(x, -1, -1, 1));
        self(self, id.back(), lst, e);

        for(int i = 0; i + 1 < (int)id.size(); ++i){
            tr[id[i]].r = id[i + 1];
            tr[id[i + 1]].l = id[i];
        }
    };
    gen(gen, 0, 0, n - 1);

    while(q--){
        int x, y;
        cin >> x >> y;
        x = st[x], y = st[y];

        auto getdist = [&](int x){
            vector<vector<int>> dist((int)tr.size(), vector<int>(2, (int)1e9));
            priority_queue<vector<int>> pq;
            pq.push({0, x, 0});
            while(!pq.empty()){
                int nd = -pq.top()[0], id = pq.top()[1], lr = pq.top()[2];
                pq.pop();
                if(nd >= dist[id][lr]){
                    continue;
                }
                dist[id][lr] = nd;
                // cout << id << ' ' << lr << ' ' << nd << endl;

                pq.push({-(nd + 1), id, 1 - lr});
                if(tr[id].l != -1 && !lr){
                    pq.push({-nd, tr[id].l, 1});
                }
                if(tr[id].r != -1 && lr){
                    pq.push({-nd, tr[id].r, 0});
                }
                if(tr[id].pr > 0 && tr[id].add == lr){
                    pq.push({-nd, tr[id].pr, lr});
                }
            }
            return dist;
        };
        auto X = getdist(x);
        auto Y = getdist(y);
        int ans = (int)1e9;
        for(int i = 0; i < (int)X.size(); ++i){
            ans = min(ans, X[i][0] + Y[i][0]);
            ans = min(ans, X[i][1] + Y[i][1]);
        }

        cout << ans - 1 << '\n';
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 902 ms 26140 KB Output is correct
3 Correct 835 ms 27808 KB Output is correct
4 Correct 780 ms 29088 KB Output is correct
5 Correct 764 ms 29628 KB Output is correct
6 Correct 754 ms 30376 KB Output is correct
7 Correct 762 ms 30656 KB Output is correct
8 Execution timed out 2057 ms 16168 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 27176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 30772 KB Time limit exceeded
2 Halted 0 ms 0 KB -