Submission #1114781

#TimeUsernameProblemLanguageResultExecution timeMemory
1114781FucKanhToll (BOI17_toll)C++14
7 / 100
50 ms29508 KiB
#include<bits/stdc++.h> #define ll long long #define int ll #define pii pair<int,int> #define p3i pair<int,pii> using namespace std; const int inf = 1e15; const int maxn = 5e4 + 2; const int maxq = 1e4 + 2; int k,n,m,q; int ans[maxq]; int d[maxn][7][7]; vector<pii> a[maxn],b[maxn]; int cv(int tk, int lvl) { return (lvl-1) * k + tk; } pii cv(int u) { return make_pair(u % k, u / k + 1); } void query(int l, int r, vector<p3i> qr) { if (qr.size()==0) return; if (l==r) { for (p3i val : qr) { int id = val.first; ans[id] = 0; } return; } for (int i = 1; i <= n; i++) { for (int u = 0; u < k; u++) { for (int v = 0; v < k; v++) { d[i][u][v] = inf; } } } int mid = l + r >> 1; for (int i = 0; i < k; i++) d[mid][i][i] = 0; for (int i = mid - 1; i >= l; i--) { for (int u = 0; u < k; u++) { int f = cv(u,i); for(pii val : a[f]) { int g,t; tie(g,t) = val; int um = cv(g).first; for (int v = 0; v < k; v++) { int h = cv(v,mid); if (cv(v,mid) >= n) continue; if (d[i+1][um][v] < inf) { d[i][u][v] = min(d[i][u][v], d[i+1][um][v] + t); // cerr << "1. from " << f << " to " << g << " to " << h << " | " << u << " " << um << " " << v << " : " << d[i][u][v] << endl; } } } } } for (int i = mid + 1; i <= r; i++) { for (int u = 0; u < k; u++) { int f = cv(u,i); if (f >= n) continue; for(pii val : b[f]) { int g,t; tie(g,t) = val; int um = cv(g).first; for (int v = 0; v < k; v++) { int h = cv(v,mid); if (h >= n) continue; if (d[i-1][v][um] < inf) { d[i][v][u] = min(d[i][v][u], d[i-1][v][um] + t); // cerr << "2. from " << h << " to " << g << " to " << f << " | " << v << " " << um << " " << u << " : " << d[i][v][u] << endl; } } } } } vector<p3i> qrl,qrr; for (p3i val : qr) { int l,r; tie(l,r) = val.second; int u,lvlu; tie(u,lvlu) = cv(l); int v,lvlv; tie(v,lvlv) = cv(r); int id = val.first; // cerr << id << ":: " << u << " " << lvlu << " " << v << " " << lvlv << endl; if (lvlv <= mid) qrl.push_back(val); else if (lvlu >mid) qrr.push_back(val); else { ans[id] = inf; for (int f = 0; f < k; f++) { ans[id] = min(ans[id], d[lvlu][u][f] + d[lvlv][f][v]); } } if (ans[id] >= inf) ans[id] = -1; } query(l,mid,qrl); query(mid+1,r,qrr); } void solve() { cin >> k >> n >> m >> q; int lvl = n / k + (n%k != 0); for (int i = 1; i <= m; i++) { int x,y,t; cin >> x >> y >> t; a[x].push_back({y,t}); b[y].push_back({x,t}); } // for (int i = 0; i < n; i++) { // cout << i << " : " << cv(i).first << " " << cv(i).second << endl; // } vector<p3i> qr; for (int i = 1; i <= q; i++){ int x,y; cin >> x >> y; qr.push_back({i,{x,y}}); } query(1,lvl,qr); for (int i = 1; i <= q; i++) { cout << ans[i] << '\n'; } } signed main() { cin.tie(0) -> sync_with_stdio(0); solve(); return 0; }

Compilation message (stderr)

toll.cpp: In function 'void query(long long int, long long int, std::vector<std::pair<long long int, std::pair<long long int, long long int> > >)':
toll.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
toll.cpp:53:25: warning: unused variable 'h' [-Wunused-variable]
   53 |                     int h = cv(v,mid);
      |                         ^
#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...