제출 #1128446

#제출 시각아이디문제언어결과실행 시간메모리
1128446Mikael639Toll (BOI17_toll)C++20
7 / 100
49 ms6468 KiB
#include <bits/stdc++.h> #define fi first #define se second #define For(i, a, b) for (int i = (a); i <= (b); ++i) #define ForD(i, a, b) for (int i = (a); i >= (b); --i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define repD(i, n) for (int i = (n) - 1; i >= 0; --i) #define coutE(x) {cout << x << '\n'; return;} #define pb push_back #define pf push_front #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define bs binary_search #define ub upper_bound #define lb lower_bound #define endl '\n' #define db long double #define ll long long #define ii pair<int, int> #define vi vector<int> #define vii vector<ii> using namespace std; void file(string s){ if (s.empty()) return; freopen((s + ".inp").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } template <class X, class Y> bool minimize(X &x, Y y){ if (x > y) return x = y, 1; return 0; } template <class X, class Y> bool maximize(X &x, Y y){ if (x < y) return x = y, 1; return 0; } const int N = 1e5 + 5; const ll LINF = 1e18; int n, k, m, q; vii g[N]; ii quer[N]; ll dist[10][N], ans[N]; bool ok(int u, int L, int R){ return L <= u/k && u/k <= R; } void dijkstra(int s, ll* dist, int L, int R){ For(i, L * k, (R + 1) * k - 1) dist[i] = LINF; priority_queue<ii, vii, greater<ii>> q; dist[s] = 0; q.push({0, s}); while (!q.empty()){ auto [d, u] = q.top(); q.pop(); if (dist[u] < d) continue; for (auto [v, w]: g[u]) if (ok(v, L, R)){ if (minimize(dist[v], dist[u] + w)){ q.push({dist[v], v}); } } } } void dnc(int L, int R, vi& idx){ if (L >= R) return; int mid = (L + R) >> 1; rep(i, k) dijkstra(mid * k + i, dist[i], L, R); vi left, right; for (int i: idx){ auto [u, v] = quer[i]; if (u/k <= mid && mid <= v/k){ rep(x, k){ minimize(ans[i], dist[x][u] + dist[x][v]); } } if (v/k < mid) left.pb(i); if (u/k > mid) right.pb(i); } if (!left.empty()) dnc(L, mid - 1, left); if (!right.empty()) dnc(mid + 1, R, right); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); file(""); cin >> k >> n >> m >> q; rep(i, m){ int u, v, w; cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } vi idx; rep(i, q){ int u, v; cin >> u >> v; ans[i] = LINF; if (u/k <= v/k){ idx.pb(i); quer[i] = {u, v}; } } dnc(0, (n - 1)/k, idx); rep(i, q) cout << (ans[i] == LINF ? -1 : ans[i]) << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void file(std::string)':
toll.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen((s + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...