제출 #1128878

#제출 시각아이디문제언어결과실행 시간메모리
1128878pcheloveksToll (BOI17_toll)C++17
8 / 100
3095 ms6000 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 = new tran(); 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]); } } } delete m1; delete m2; 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) out.push_back(-1); 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...