제출 #1217604

#제출 시각아이디문제언어결과실행 시간메모리
1217604trimkusRailway Trip 2 (JOI22_ho_t4)C++20
8 / 100
2095 ms589824 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = double; const int LOG = 21; const int MAXM = 1e5; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, m; cin >> n >> k >> m; vector<vector<int>> adj(n + 1); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; if (a < b) { int till = min(b - 1, a + k - 1); for (int j = a; j <= till; ++j) { for (int k = j + 1; k <= b; ++k) { adj[j].push_back(k); } } } else { int till = max(b + 1, a - k + 1); for (int j = a; j >= till; --j) { for (int k = j - 1; k >= b; --k) { adj[j].push_back(k); } } } } for (int i = 1; i <= n; ++i) { sort(begin(adj[i]), end(adj[i])); adj[i].erase(unique(begin(adj[i]), end(adj[i])), end(adj[i])); //~ cout << adj[i].size() << "\n"; } vector<vector<int>> dist(n + 1, vector<int>(n + 1, 1000000)); for (int i = 1; i <= n; ++i) { dist[i][i] = 0; for (auto& u : adj[i]) { dist[i][u] = 1; } } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } //~ for (int i = 1; i <= n; ++i) { //~ for (int j = 1; j <= n; ++j) { //~ cout << dist[i][j] << " "; //~ } //~ cout << "\n"; //~ } int q; cin >> q; while (q--) { int a, b; cin >> a >> b; cout << (dist[a][b] >= 1000000 ? -1 : dist[a][b]) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...