Submission #1128874

#TimeUsernameProblemLanguageResultExecution timeMemory
1128874pcheloveksToll (BOI17_toll)C++17
0 / 100
3093 ms4244 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("avx,avx2,tune=native") #include <iostream> #include <vector> #include <map> #include <set> #include <fstream> #include <algorithm> #include <cstring> // Для memset #define endl '\n' using namespace std; typedef long long LL; typedef pair<LL, LL> pii; const LL DIM = 50007; const LL INF = 999999999999; LL n, k, o, m; class edge { public: LL to, w; }; vector < edge > v[DIM]; class tran { public: LL mat[5][5]; void init() { for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { mat[i][j] = INF; } } } }; tran solve(LL L, LL R) { tran ans; ans.init(); if (R - L == 1) { for (int i = 0; i < k; i++) { LL val = L * k + i; for (auto to : v[val]) { ans.mat[i][to.to - (R * k)] = to.w; } } return ans; } LL mid = (L + R) / 2; tran m1 = solve(L, mid); tran m2 = solve(mid, R); for (int l = 0; l < k; l++) { for (int r = 0; r < k; r++) { for (int m = 0; m < k; m++) { ans.mat[l][r] = min(ans.mat[l][r], m1.mat[l][m] + m2.mat[m][r]); } } } return ans; } LL a, b, res, b1, b2; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> n >> m >> o; for (int i = 1; i <= m; i++) { LL a, b, t; cin >> a >> b >> t; v[a].push_back({ b, t }); } vector < LL > out; for (int i = 1; i <= o; i++) { cin >> a >> b; b1 = a / k; b2 = b / k; if (b1 >= b2) cout << -1 << endl; else { res = solve(b1, b2).mat[a - b1 * k][b - b2 * k]; if (res >= INF) out.push_back(-1); else out.push_back(res); } } for (auto x : out) cout << x << endl; 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...