Submission #626227

#TimeUsernameProblemLanguageResultExecution timeMemory
626227valerikkEscape Route (JOI21_escape_route)C++17
0 / 100
1306 ms180120 KiB
#include "escape_route.h" #include <algorithm> #include <iostream> using std::vector; using std::pair; using ll = long long; const ll INF = 1e18; vector<ll> dijkstra(int N, ll S, int st, ll T, vector<vector<ll>> &l, vector<vector<ll>> &c) { vector<ll> t(N, INF); vector<bool> used(N, 0); t[st] = T; while (1) { int u = 0; for (int i = 1; i < N; ++i) { if (make_pair(used[i], t[i]) < make_pair(used[u], t[u])) u = i; } if (used[u] || t[u] == INF) break; used[u] = 1; for (int v = 0; v < N; ++v) { if (!used[v] && l[u][v] < S) { ll t1 = t[u] + l[u][v]; if (t[u] % S + l[u][v] > c[u][v]) t1 += S - t1 % S; t[v] = std::min(t[v], t1); } } } return t; } vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) { vector<vector<ll>> l(N, vector<ll>(N, S)); vector<vector<ll>> c(N, vector<ll>(N, S)); for (int i = 0; i < M; ++i) { l[A[i]][B[i]] = l[B[i]][A[i]] = L[i]; c[A[i]][B[i]] = c[B[i]][A[i]] = C[i]; } for (int i = 0; i < N; ++i) { l[i][i] = 0; c[i][i] = 0; } vector<vector<vector<ll>>> t(N, vector<vector<ll>>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (l[i][j] < S) t[i][j] = dijkstra(N, S, j, c[i][j], l, c); } } vector<ll> ans(Q); for (int i = 0; i < Q; ++i) { ans[i] = t[U[i]][U[i]][V[i]] + (S - T[i]) % S; } for (int st = 0; st < N; ++st) { vector<pair<ll, int>> que; for (int i = 0; i < Q; ++i) { if (U[i] == st) que.push_back({T[i], i}); } std::sort(que.rbegin(), que.rend()); vector<vector<pair<ll, int>>> ord(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i != j && l[i][j] < S) ord[i].push_back({c[i][j] - l[i][j], j}); } std::sort(ord[i].rbegin(), ord[i].rend()); } vector<int> ind(N, 0); vector<ll> d(N, INF); d[st] = 0; int ptr = 0; while (1) { pair<ll, int> max = {-1, -1}; for (int i = 0; i < N; ++i) { if (ind[i] < ord[i].size()) max = std::max(max, {ord[i][ind[i]].first - d[i], i}); } while (ptr < que.size() && que[ptr].first > max.first) { int id = que[ptr++].second; // std::cerr << id << " " << d[V[id]] << "\n"; ans[id] = std::min(ans[id], d[V[id]]); for (int i = 0; i < N; ++i) { if (d[i] < INF) ans[id] = std::min(ans[id], S + t[i][i][V[id]] - T[id]); } } if (max.first < 0) break; int u = max.second; int v = ord[u][ind[u]++].second; for (int i = 0; i < N; ++i) { if (t[u][v][i] <= S) d[i] = std::min(d[i], t[u][v][i] - max.first); } } } return ans; }

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:84:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (ind[i] < ord[i].size())
escape_route.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    while (ptr < que.size() && que[ptr].first > max.first) {
      |           ~~~~^~~~~~~~~~~~
#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...