Submission #1212716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212716		abczz	Escape Route (JOI21_escape_route)	C++20	0 / 100	707 ms	294976 KiB

escape_route

#include "escape_route.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

vector <array<ll, 4>> query;
ll adjid[90];
vector <array<ll, 3>> adj[90];
array <ll, 3> par_edge[90];
vector <array<ll, 3>> tree_edge[90][2];
vector <array<ll, 2>> queryb[90][90];
vector <array<ll, 3>> querya[90];
ll dist[90], X[90], fullday[90][90], reachable[90][90];
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
priority_queue <array<ll, 2>> rpq;
ll n, q, s;
vector <ll> F;

std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
    std::vector<int> V, std::vector<long long> T) {
  n = N, q = Q, s = S;
  F.resize(q);
  for (int i=0; i<M; ++i) {
    adj[A[i]].push_back({B[i], C[i]-L[i], L[i]});
    adj[B[i]].push_back({A[i], C[i]-L[i], L[i]});
  }
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) dist[j] = 1e18, X[j] = -1e18;
    pq.push({0, i, 0});
    dist[i] = 0, X[i] = s-1;
    while (!pq.empty()) {
      auto [w, u, t] = pq.top();
      pq.pop();
      if (dist[u] != w) continue;
      for (auto [v, lim, len] : adj[u]) {
        if (t <= lim && dist[v] > w+len) { 
          dist[v] = w+len;
          pq.push({dist[v], v, t+len});
        }
        else if (t > lim && dist[v] > w+s-t+len) {
          dist[v] = w+s-t+len;
          pq.push({dist[v], v, len});
        }
      }
    }
    for (int j=0; j<N; ++j) fullday[i][j] = dist[j];
    rpq.push({s-1, i});
    while (!rpq.empty()) {
      auto [w, u] = rpq.top();
      rpq.pop();
      if (X[u] != w) continue;
      reachable[u][i] = X[u];
      for (auto [v, lim, len] : adj[u]) {
        if (X[v] < min(lim, X[u]-len)) {
          X[v] = min(lim, X[u]-len);
          rpq.push({X[v], v});
        }
      }
    }
    sort(adj[i].begin(), adj[i].end(), [](auto a, auto b) {
      return a[1] < b[1];
    });
  }
  for (int i=0; i<q; ++i) query.push_back({U[i], V[i], T[i], i});
  sort(query.begin(), query.end(), [](auto a, auto b) {
    return a[2] > b[2];
  });
  for (int i=0; i<q; ++i) {
    if (reachable[query[i][0]][query[i][1]] >= query[i][2]) querya[query[i][0]].push_back({query[i][1], query[i][2], query[i][3]});
    else queryb[query[i][0]][query[i][1]].push_back({query[i][2], query[i][3]});
  }
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
      vector <array<ll, 2>> cur;
      for (int k=0; k<n; ++k) {
        if (reachable[i][k] >= 0) cur.push_back({reachable[i][k], fullday[k][j]});
      }
      ll f = 1e18;
      sort(cur.begin(), cur.end());
      for (auto [t, id] : queryb[i][j]) {
        while (!cur.empty() && cur.back()[0] >= t) {
          f = min(f, cur.back()[1]);
          cur.pop_back();
        }
        F[id] = f+S-t;
      }
    }
  }
  for (int i=0; i<n; ++i) {
    ll p = S-1;
    reverse(querya[i].begin(), querya[i].end());
    for (int j=0; j<n; ++j) adjid[j] = adj[j].size()-1;
    while (!querya[i].empty()) {
      ll newp = -1;
      for (int j=0; j<n; ++j) {
        dist[j] = 1e18, par_edge[j] = {-1, -1, -1};
        swap(tree_edge[j][0], tree_edge[j][1]);
        tree_edge[j][1].clear();
      }
      dist[i] = p;
      pq.push({p, i, 0});
      while (!pq.empty()) {
        auto [w, u, t] = pq.top();
        pq.pop();
        if (dist[u] != w) continue;
        if (par_edge[u][0] != -1) tree_edge[par_edge[u][0]][1].push_back({u, par_edge[u][1], par_edge[u][2]});
        while (adjid[u] >= 0 && adj[u][adjid[u]][1] >= dist[u]) {
          tree_edge[u][0].push_back(adj[u][adjid[u]]);
          --adjid[u];
        }
        if (adjid[u] >= 0) newp = max(newp, p-dist[u]+adj[u][adjid[u]][1]);
        for (auto [v, lim, len] : tree_edge[u][0]) {
          if (dist[v] > w+len) {
            dist[v] = w+len;
            par_edge[v] = {u, lim, len};
            pq.push({dist[v], v, 0});
          }
        }
      }
      while (!querya[i].empty() && newp < querya[i].back()[1] && querya[i].back()[1] <= p) {
        F[querya[i].back()[2]] = dist[querya[i].back()[0]]-p;
        querya[i].pop_back();
      }
      if (newp == -1) break;
      p = newp;
    }
  }
  return F;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30