Submission #1158887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158887		vladilius	Railway Trip (JOI17_railway_trip)	C++20	0 / 100	484 ms	59404 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k, q; cin>>n>>k>>q;
    vector<int> a(n + 1), d[k + 1];
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        d[a[i]].pb(i);
    }
    
    vector<int> g[n + 1];
    set<int> st;
    for (int i = k; i > 0; i--){
        for (int j: d[i]) st.insert(j);
        for (int j: d[i]){
            auto it = st.find(j);
            if (it != prev(st.end())){
                auto it1 = next(it);
                g[j].pb(*it1);
                g[*it1].pb(j);
            }
            if (it != st.begin()){
                auto it1 = prev(it);
                g[j].pb(*it1);
                g[*it1].pb(j);
            }
        }
    }
    
    mt19937 rng((int) time(0));
    vector<vector<int>> dist(n + 1, vector<int>(100, 1e9));
    queue<int> Q;
    for (int tt = 0; tt < 100; tt++){
        int x = rng() % n + 1;
        dist[x][tt] = 0; Q.push(x);
        while (!Q.empty()){
            int v = Q.front(); Q.pop();
            for (int u: g[v]){
                if (dist[u][tt] == 1e9){
                    dist[u][tt] = dist[v][tt] + 1;
                    Q.push(u);
                }
            }
        }
    }

    while (q--){
        int x, y; cin>>x>>y;
        int out = 1e9;
        for (int i = 0; i < 100; i++){
            out = min(out, dist[x][i] + dist[y][i]);
        }
        out--;
        cout<<out<<"\n";
    }
}

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