Submission #1142598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142598		OI_Account	Railway Trip (JOI17_railway_trip)	C++20	20 / 100	2096 ms	8260 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

const int N = 100'000;
const int M = 18;
const int INF = 1'000'000'000;

int n,k,  q, a[N + 10];
int nxt[2][N + 10], h[N + 10];
int rmq[2][N + 10][M + 2];
vector<int> adj[N + 10];

void readInput() {
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

void calcLft() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] < a[i])
            st.pop();
        nxt[0][i] = (st.size()? st.top(): 0);
        st.push(i);
    }
}

void calcRght() {
    stack<int> st;
    for (int i = n; i >= 1; i--) {
        while (st.size() && a[st.top()] < a[i])
            st.pop();
        nxt[1][i] = (st.size()? st.top(): 0);
        st.push(i);
    }
}

void calcRMQ() {
    for (int t = 0; t < 2; t++) {
        for (int i = 1; i <= n; i++)
            rmq[t][i][0] = nxt[t][i];
        for (int j = 1; j <= M; j++)
            for (int i = 1; i <= n; i++)
                rmq[t][i][j] = rmq[t][rmq[t][i][j - 1]][j - 1];
    }
}

int disL(int u, int v) {
    int sum = 0;
    for (int j = M; j >= 0; j--)
        if (rmq[0][u][j] && v < rmq[0][u][j]) {
            u = rmq[0][u][j];
            sum += (1 << j);
        }
    return (nxt[0][u] == v? sum + 1: INF);
}

int disR(int u, int v) {
    int sum = 0;
    for (int j = M; j >= 0; j--)
        if (rmq[1][u][j] && rmq[1][u][j] < v) {
            u = rmq[1][u][j];
            sum += (1 << j);
        }
    return (nxt[1][u] == v? sum + 1: INF);
}

int dis(int u, int tu, int v) {
    if (u == v)
        return 0;
    return (tu == 0? disL(u, v): disR(u, v));
}

/*int dis(int u, int tu, int v, int tv) {
    int sum = 0
    for (int j = M; j >= 0; j--) {
        int x = rmq[tu][u][j];
        int y = rmq[tv][v][j];
        if (x && y && x != y) {
            sum += (1 << j) + (1 << j);
            u = x;
            v = y;
        }
    }
    return (nxt[tu][u] && nxt[tu][u] == nxt[tv][v]? sum + 1: INF);
}*/

int dis(int u, int tu, int v, int tv) {
    cout << u << ' ' << tu << ' ' << v << ' ' << tv << ": start " << nxt[tu][u] << endl;
    int sum = 0;
    for (int j = M; j >= 0; j--) {
        int x = rmq[tu][u][j];
        if (x && dis(v, tv, x) == INF) {
            sum += (1 << j);
            u = x;
        }
    }
    if (nxt[tu][u]) {
        int d = dis(v, tv, nxt[tu][u]);
        cout << u << ' ' << tu << ' ' << v << ' ' << tv << ": " << nxt[tu][u] << endl;
        if (d == INF)
            return INF;
        return sum + d + 1;
    }
    return INF;
}

/*int chechL(int u, int v) {
    int lca = getMax()
}*/

void query() {
    int u, v;
    cin >> u >> v;
    if (u > v)
        swap(u, v);
    int ans = INF; //min({chechL(u, v), checkMid(u, v), checkR(u, v)});
    for (int tu = 0; tu < 2; tu++)
        for (int tv = 0; tv < 2; tv++)
            ans = min(ans, dis(u, tu, v, tv));
    cout << ans - 1 << flush;
}

void BFS(int src) {
    for (int i = 1; i <= n; i++)    
        h[i] = 0;
    queue<int> qu;
    h[src] = 1;
    qu.push(src);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (auto v: adj[u])
            if (!h[v]) {
                h[v] = h[u] + 1;
                qu.push(v);
            }
    }
}

void query2() {
    int u, v;
    cin >> u >> v;
    BFS(u);
    cout << h[v] - 2 << '\n';
}

void addEdge(int u, int v) {
    if (v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        addEdge(i, nxt[0][i]);
        addEdge(i, nxt[1][i]);
    }
    while (q--)
        query2();
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcLft();
    calcRght();
    //calcRMQ();
    solve();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55