oj.uz

Submission #620487

# Submission time Handle Problem Language Result Execution time Memory
620487 2022-08-03T06:26:19 Z 박상훈(#8517) Railway Trip (JOI17_railway_trip) C++17
100 / 100
 285 ms 89312 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Cost{
    int a[2][2];
    Cost operator + (const Cost &C) const{
        Cost ret;
        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                ret.a[i][j] = 1e9;
                for (int k=0;k<2;k++){
                    ret.a[i][j] = min(ret.a[i][j], a[i][k] + C.a[k][j]);
                }
            }
        }
        return ret;
    }
};
int n, k, q, a[100100];
vector<int> R[100100];


int cnt;
int idx[200200], par[200200], pos[200200], sz[200200], dep[200200];
Cost paw[200200];
void build_tree(int l, int r, int parent){
    vector<pair<int, int>> child;
    int s = l;
    while(s<r){
        assert(R[s].back()<=r);
        child.emplace_back(s, R[s].back());
        R[s].pop_back();
        s = child.back().second;
    }

    for (int i=0;i<(int)child.size();i++){
        auto [s, e] = child[i];
        ++cnt; ///current vertex number
        if (s+1==e) idx[s] = cnt;
        assert(cnt<200200);
        //printf("%d %d -> %d\n", s, e, cnt);

        dep[cnt] = dep[parent] + 1;
        par[cnt] = parent;
        paw[cnt].a[0][0] = i;
        paw[cnt].a[1][1] = (int)child.size()-1-i;
        paw[cnt].a[0][1] = paw[cnt].a[1][0] = min(paw[cnt].a[0][0], paw[cnt].a[1][1]) + 1;
        pos[cnt] = i;

        if (s+1 < e) build_tree(s, e, cnt);
    }
    sz[parent] = child.size();
}

int sp1[20][200200];
Cost sp2[20][200200];
void build_sparse_table(){
    for (int i=1;i<=cnt;i++){
        sp1[0][i] = par[i];
        sp2[0][i] = paw[i];
    }

    for (int j=1;j<20;j++){
        for (int i=1;i<=cnt;i++){
            sp1[j][i] = sp1[j-1][sp1[j-1][i]];
            if (!sp1[j][i]) continue;
            sp2[j][i] = sp2[j-1][i] + sp2[j-1][sp1[j-1][i]];
        }
    }
}

void init(){
    vector<int> st;
    for (int i=1;i<=n;i++){
        while(!st.empty() && a[st.back()] <= a[i]){
            R[st.back()].push_back(i);
            st.pop_back();
        }
        st.push_back(i);
    }
    assert(st.size()==1);
    st.pop_back();

    for (int i=n;i;i--){
        while(!st.empty() && a[st.back()] <= a[i]){
            if (a[st.back()]!=a[i]){
                R[i].push_back(st.back());
            }
            st.pop_back();
        }
        st.push_back(i);
    }

    for (int i=1;i<=n;i++){
        sort(R[i].begin(), R[i].end());
        R[i].erase(unique(R[i].begin(), R[i].end()), R[i].end());
    }

    build_tree(1, n, 0);
    build_sparse_table();
}

void update(int a[], Cost T){
    int ret[2];
    ret[0] = min(a[0] + T.a[0][0], a[1] + T.a[1][0]);
    ret[1] = min(a[0] + T.a[0][1], a[1] + T.a[1][1]);
    a[0] = ret[0], a[1] = ret[1];
}

int dist(int u, int v){
    if (u>v) swap(u, v);
    if (u+1==v) return 1;

    int au[2] = {0, 1}, av[2] = {0, 1};
    if (v==n){
        v = idx[n-1];
        swap(av[0], av[1]);
    }
    else v = idx[v];

    u = idx[u];

    if (dep[u] < dep[v]){
        swap(u, v);
        swap(au[0], av[0]);
        swap(au[1], av[1]);
    }


    if (dep[u]>dep[v]){
        for (int j=19;j>=0;j--) if (dep[sp1[j][u]] > dep[v]){
            update(au, sp2[j][u]);
            u = sp1[j][u];
        }
        update(au, paw[u]);
        u = par[u];
    }

    assert(u!=v);
    assert(dep[u]==dep[v]);

    if (par[u]!=par[v]){
        for (int j=19;j>=0;j--) if (par[sp1[j][u]]!=par[sp1[j][v]]){
            update(au, sp2[j][u]);
            update(av, sp2[j][v]);
            u = sp1[j][u];
            v = sp1[j][v];
        }
        update(au, paw[u]);
        update(av, paw[v]);
        u = par[u]; v = par[v];
    }

    assert(u!=v);
    assert(par[u]==par[v]);

    int ret;
    if (pos[u] < pos[v]) ret = (pos[v]-pos[u]-1) + au[1] + av[0];
    else ret = (pos[u]-pos[v]-1) + av[1] + au[0];

    if (par[u]){
        update(au, paw[u]);
        update(av, paw[v]);
        ret = min(ret, au[0] + av[0]);
        ret = min(ret, au[1] + av[1]);
    }
    return ret;
}

/*
int dist[100100];
bool visited[100100];
void bfs(int s){
    fill(dist+1, dist+n+1, 1e9);
    fill(visited+1, visited+n+1, 0);
    dist[s] = 0;
    visited[s] = 1;
    queue<int> q;
    q.push(s);

    while(!q.empty()){
        int v = q.front(); q.pop();
        for (auto &nxt:adj[v]) if (!visited[nxt]){
            dist[nxt] = dist[v] + 1;
            visited[nxt] = 1;
            q.push(nxt);
        }
    }
}*/

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for (int i=1;i<=n;i++){
        scanf("%d", a+i);
    }

    init();
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", dist(x, y)-1);
    }
    return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:195:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~
railway_trip.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2792 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2796 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct
9 Correct 2 ms 2792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 50 ms 33892 KB Output is correct
3 Correct 57 ms 37864 KB Output is correct
4 Correct 53 ms 39856 KB Output is correct
5 Correct 55 ms 40684 KB Output is correct
6 Correct 56 ms 43968 KB Output is correct
7 Correct 56 ms 44780 KB Output is correct
8 Correct 30 ms 18996 KB Output is correct
9 Correct 67 ms 56020 KB Output is correct
10 Correct 54 ms 49268 KB Output is correct
11 Correct 64 ms 53692 KB Output is correct
12 Correct 60 ms 53664 KB Output is correct
13 Correct 61 ms 53624 KB Output is correct
14 Correct 66 ms 53668 KB Output is correct
15 Correct 64 ms 53640 KB Output is correct
16 Correct 56 ms 53716 KB Output is correct
17 Correct 61 ms 45136 KB Output is correct
18 Correct 80 ms 45004 KB Output is correct
19 Correct 60 ms 52720 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 36736 KB Output is correct
2 Correct 158 ms 34536 KB Output is correct
3 Correct 181 ms 37136 KB Output is correct
4 Correct 153 ms 37480 KB Output is correct
5 Correct 170 ms 37964 KB Output is correct
6 Correct 180 ms 38360 KB Output is correct
7 Correct 205 ms 38520 KB Output is correct
8 Correct 122 ms 23356 KB Output is correct
9 Correct 69 ms 19972 KB Output is correct
10 Correct 76 ms 26140 KB Output is correct
11 Correct 71 ms 26088 KB Output is correct
12 Correct 78 ms 26148 KB Output is correct
13 Correct 78 ms 26100 KB Output is correct
14 Correct 120 ms 26248 KB Output is correct
15 Correct 122 ms 26692 KB Output is correct
16 Correct 139 ms 30016 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 45252 KB Output is correct
2 Correct 187 ms 45248 KB Output is correct
3 Correct 206 ms 45084 KB Output is correct
4 Correct 179 ms 45192 KB Output is correct
5 Correct 62 ms 19856 KB Output is correct
6 Correct 214 ms 56636 KB Output is correct
7 Correct 200 ms 57968 KB Output is correct
8 Correct 158 ms 51068 KB Output is correct
9 Correct 196 ms 55700 KB Output is correct
10 Correct 213 ms 55644 KB Output is correct
11 Correct 201 ms 55500 KB Output is correct
12 Correct 205 ms 55540 KB Output is correct
13 Correct 207 ms 55540 KB Output is correct
14 Correct 235 ms 72884 KB Output is correct
15 Correct 246 ms 79184 KB Output is correct
16 Correct 285 ms 89312 KB Output is correct
17 Correct 242 ms 62600 KB Output is correct
18 Correct 255 ms 62612 KB Output is correct
19 Correct 225 ms 61948 KB Output is correct
20 Correct 208 ms 48816 KB Output is correct
21 Correct 194 ms 46816 KB Output is correct
22 Correct 215 ms 47008 KB Output is correct
23 Correct 241 ms 52480 KB Output is correct