Submission #1092705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092705		ortsac	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	2098 ms	524288 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
vector<int> adj[MAXN];

int32_t main() {
    int n, x, m;
    cin >> n >> x >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (a < b) {
            for (int j = a; j <= min(a + x - 1, b); j++) {
                for (int k = j; k <= b; k++) adj[j].push_back(k);
            }
        } else {
            for (int j = a; j >= max(a - x + 1, b); j--) {
                for (int k = j; k >= b; k--) adj[j].push_back(k);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        vector<bool> vis(n + 1);
        vector<int> d(n + 1);
        vis[s] = 1;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (vis[v]) continue;
                vis[v] = 1;
                d[v] = (d[u] + 1);
                q.push(v);
            }
        }
        if (!vis[t]) cout << "-1\n";
        else cout << d[t] << "\n";
    }
}

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