oj.uz

Submission #620463

# Submission time Handle Problem Language Result Execution time Memory
620463 2022-08-03T06:16:25 Z 박상훈(#8517) Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 17812 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Cost{
    int a[2][2];
};
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();
}

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);
}

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]);
    }


    while(dep[u]>dep[v]){
        update(au, paw[u]);
        u = par[u];
    }

    assert(u!=v);
    while(par[u]!=par[v]){
        update(au, paw[u]);
        update(av, paw[v]);
        u = par[u]; v = 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:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~
railway_trip.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2660 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 30 ms 12356 KB Output is correct
3 Correct 28 ms 12748 KB Output is correct
4 Correct 30 ms 13044 KB Output is correct
5 Correct 31 ms 13136 KB Output is correct
6 Correct 31 ms 13220 KB Output is correct
7 Correct 34 ms 13288 KB Output is correct
8 Correct 17 ms 10356 KB Output is correct
9 Correct 27 ms 16044 KB Output is correct
10 Correct 23 ms 13552 KB Output is correct
11 Correct 28 ms 14040 KB Output is correct
12 Correct 39 ms 14060 KB Output is correct
13 Correct 39 ms 14152 KB Output is correct
14 Correct 28 ms 14040 KB Output is correct
15 Correct 28 ms 14104 KB Output is correct
16 Correct 27 ms 14152 KB Output is correct
17 Correct 33 ms 13264 KB Output is correct
18 Correct 33 ms 13260 KB Output is correct
19 Correct 39 ms 13748 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13848 KB Output is correct
2 Correct 81 ms 13948 KB Output is correct
3 Correct 74 ms 14208 KB Output is correct
4 Correct 68 ms 14204 KB Output is correct
5 Correct 86 ms 14348 KB Output is correct
6 Correct 74 ms 14292 KB Output is correct
7 Correct 113 ms 14344 KB Output is correct
8 Correct 56 ms 12468 KB Output is correct
9 Correct 51 ms 11328 KB Output is correct
10 Correct 65 ms 11304 KB Output is correct
11 Correct 49 ms 11312 KB Output is correct
12 Correct 67 ms 11388 KB Output is correct
13 Correct 53 ms 11356 KB Output is correct
14 Correct 63 ms 11444 KB Output is correct
15 Correct 58 ms 11460 KB Output is correct
16 Correct 76 ms 12108 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14704 KB Output is correct
2 Correct 94 ms 15060 KB Output is correct
3 Correct 81 ms 14924 KB Output is correct
4 Correct 104 ms 14964 KB Output is correct
5 Correct 60 ms 11276 KB Output is correct
6 Execution timed out 2091 ms 17812 KB Time limit exceeded
7 Halted 0 ms 0 KB -