Submission #695334

#TimeUsernameProblemLanguageResultExecution timeMemory
695334daoquanglinh2007Toll (BOI17_toll)C++17
100 / 100
212 ms40428 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair <int, int> #define fi first #define se second #define mp make_pair const int NM = 50000; const ll INF = 1e18; struct matrix{ int M, N; ll grid[5][5]; void init(int x, int y, ll val){ M = x, N = y; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) grid[i][j] = val; } matrix operator * (matrix b){ matrix a = *this; matrix c; c.init(a.M, b.N, +INF); for (int i = 0; i < c.M; i++) for (int j = 0; j < c.N; j++) for (int k = 0; k < a.N; k++) c.grid[i][j] = min(c.grid[i][j], a.grid[i][k]+b.grid[k][j]); return c; } }; int K, N, M, O, nLayer; map <pii, ll> d; matrix A[NM+5]; matrix st[4*NM+5]; ll dist(int a, int b){ if (a == b) return 0; if (d.count(mp(a, b)) == 0) return +INF; return d[mp(a, b)]; } matrix iden(int k){ matrix a; a.init(k, k, +INF); for (int i = 0; i < k; i++) a.grid[i][i] = 0; return a; } void build(int id, int l, int r){ st[id].init(K, K, 0); if (l == r){ st[id] = A[l]; return; } int mid = (l+r)/2; build(2*id, l, mid); build(2*id+1, mid+1, r); st[id] = st[2*id]*st[2*id+1]; } matrix get(int id, int l, int r, int u, int v){ if (u > v || v < l || u > r) return iden(K); if (l >= u && r <= v) return st[id]; int mid = (l+r)/2; return get(2*id, l, mid, u, v)*get(2*id+1, mid+1, r, u, v); } void solveQuery(int a, int b){ int l = a/K, r = b/K; if (l >= r){ cout << "-1\n"; return; } matrix C; C.init(1, K, +INF); for (int i = 0; i < K; i++) C.grid[0][i] = dist(a, (l+1)*K+i); C = C*get(1, 0, nLayer-2, l+1, r-1); ll ans = C.grid[0][b%K]; if (ans >= +INF) ans = -1; cout << ans << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> K >> N >> M >> O; nLayer = N/K+(N%K > 0); for (int i = 0; i <= nLayer-2; i++) A[i].init(K, K, +INF); while (M--){ int a, b; ll t; cin >> a >> b >> t; d[mp(a, b)] = t; A[a/K].grid[a%K][b%K] = t; } build(1, 0, nLayer-2); while (O--){ int a, b; cin >> a >> b; solveQuery(a, b); } return 0; }
#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...