Submission #1267788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267788		gustavo_d	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	715 ms	589824 KiB

Main

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

const int MAXN = 1e5;

vector<int> adj[MAXN];
int dist[MAXN];
int l[MAXN], r[MAXN];
bool vis[MAXN];
vector<int> updL[MAXN], updR[MAXN];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, k; cin >> n >> k;
    int m; cin >> m;
    for (int i=0; i<m; i++) {
        int a, b; cin >> a >> b; a--; b--;
        if (a <= b) {
            // r[a...min(b, a+k-1)] = max(b)
            // cout << "r: " << a << ' ' << min(b, a+k-1) << '=' << b << endl;
            updR[a].push_back(b);
            updR[min(b, a+k-1)].push_back(-b);
        } else {
            // l[max(b, a-k+1)...a] = min(a)
            // cout << "l: " << max(b, a-k+1) << ' ' << a << '=' << b << endl;
            updL[max(b, a-k+1)].push_back(b);
            updL[a].push_back(-b);
        }
    }
    multiset<int> pfL, pfR;
    for (int i=0; i<n; i++) {
        for (int x : updL[i]) {
            if (x < 0) continue;
            pfL.insert(x);
        }
        for (int x : updR[i]) {
            if (x < 0) continue;
            pfR.insert(x);
        }

        l[i] = (pfL.empty() ? i : *pfL.begin());
        r[i] = (pfR.empty() ? i : *pfR.rbegin());

        for (int x : updL[i]) {
            if (x > 0) continue;
            pfL.erase(pfL.find(-x));
        }
        for (int x : updR[i]) {
            if (x > 0) continue;
            pfR.erase(pfR.find(-x));
        }
    }

    for (int i=0; i<n; i++) {
        // cout << l[i] << ' ' << r[i] << endl;
        for (int j=l[i]; j<=r[i]; j++) {
            adj[i].push_back(j);
        }
    }

    int qs; cin >> qs;
    for (int q=0; q<qs; q++) {
        int src, dest; cin >> src >> dest;
        src--; dest--;
        if (src == dest) {
            cout << 0 << endl;
            continue;
        }
        dist[src] = 1;
        queue<int> visit;
        for (int i=0; i<n; i++) vis[i] = false;
        vis[src] = true;
        bool found = false; visit.push(src);
        while (!visit.empty()) {
            int v = visit.front();
            visit.pop();
            // cout << v << endl;
            if (l[v] <= dest and dest <= r[v]) {
                cout << dist[v] << '\n';
                found = true;
                break;
            }
            for (int viz : adj[v]) {
                if (vis[viz]) continue;
                visit.push(viz);
                vis[viz] = true;
                dist[viz] = dist[v] + 1;
            }
        }
        if (!found) cout << -1 << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13