Submission #735697

#TimeUsernameProblemLanguageResultExecution timeMemory
735697QwertyPiEscape Route (JOI21_escape_route)C++17
25 / 100
9097 ms231240 KiB
#include "escape_route.h" #include <bits/stdc++.h> #define int long long #define INF (1LL << 60) using namespace std; const int N = 101; struct timestamp{ int day = N, byou = 0; bool operator< (const timestamp& o) const { return day > o.day || day == o.day && byou < o.byou; } }; struct edge{ int to, l, c; }; vector<edge> G[N]; int S; int norm(int x){ return (x % S + S) % S; } vector<pair<int, int>> Ti[N][N]; int D[N][N]; void add_data(int x, int y, int tx, int ty){ if(tx <= -(INF >> 1) || ty >= (INF >> 1)) return; int rtx = ((tx % S) + S) % S; int rty = ty + rtx - tx; int tot = rty - rtx; Ti[x][y].push_back({rtx, tot}); } vector<int> from(int x, int t){ vector<int> d(N, -INF); d[x] = t; priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq; pq.push({t, x}); while(!pq.empty()){ auto [t, v] = pq.top(); pq.pop(); if(d[v] != t) continue; for(auto [to, l, c] : G[v]){ int tp = norm(t), nt; if(tp > c){ // back to c nt = t - (tp - c) - l; }else if(tp >= l){ // ok nt = t - l; }else{ // no last day nt = -INF; } if(nt > d[to]){ d[to] = nt; pq.push({nt, to}); } } } return d; } vector<int> to(int x, int t, bool allow_midnight){ vector<int> d(N, INF); d[x] = t; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({t, x}); while(!pq.empty()){ auto [t, v] = pq.top(); pq.pop(); if(d[v] != t) continue; for(auto [to, l, c] : G[v]){ int tp = norm(t), nt; if(tp > c - l){ // next day nt = allow_midnight ? t + (S - tp) + l : INF; }else{ // ok nt = t + l; } if(nt < d[to]){ d[to] = nt; pq.push({nt, to}); } } } return d; } vector<int> calculate_necessary_time(int32_t N, int32_t M, int S, int32_t Q, vector<int32_t> A, vector<int32_t> B, vector<int> L, vector<int> C, vector<int32_t> U, vector<int32_t> V, vector<int> T) { ::S = S; for(int i = 0; i < M; i++){ G[A[i]].push_back({B[i], L[i], C[i]}); G[B[i]].push_back({A[i], L[i], C[i]}); } for(int i = 0; i < M; i++){ vector<int> d1, d2; d1 = from(A[i], C[i] - L[i]); d2 = to(B[i], C[i], false); for(int x = 0; x < N; x++){ for(int y = 0; y < N; y++){ add_data(x, y, d1[x], d2[y]); } } d1 = from(B[i], C[i] - L[i]); d2 = to(A[i], C[i], false); for(int x = 0; x < N; x++){ for(int y = 0; y < N; y++){ add_data(x, y, d1[x], d2[y]); } } } for(int i = 0; i < N; i++){ vector<int> d = to(i, 0, true); for(int j = 0; j < N; j++){ D[i][j] = d[j]; } } for(int u = 0; u < N; u++){ for(int v = 0; v < N; v++){ vector<pair<int, int>> vp; sort(Ti[u][v].begin(), Ti[u][v].end()); for(auto [tx, tot] : Ti[u][v]){ while(!vp.empty() && vp.back().second >= tot) vp.pop_back(); if(!vp.empty() && vp.back().first == tx) continue; vp.push_back({tx, tot}); } Ti[u][v] = vp; } } vector<int> ans(Q, INF); for(int i = 0; i < Q; i++){ ans[i] = S - T[i] + D[U[i]][V[i]]; for(int m = 0; m < N; m++){ auto ptr = lower_bound(Ti[U[i]][m].begin(), Ti[U[i]][m].end(), pair<int, int>{T[i], 0}); if(ptr != Ti[U[i]][m].end()){ ans[i] = min(ans[i], m == V[i] ? ptr->second : S - T[i] + D[m][V[i]]); } } } return ans; }

Compilation message (stderr)

escape_route.cpp: In member function 'bool timestamp::operator<(const timestamp&) const':
escape_route.cpp:12:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |   return day > o.day || day == o.day && byou < o.byou;
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
#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...