Submission #1213218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213218		abczz	Escape Route (JOI21_escape_route)	C++20	100 / 100	7701 ms	1390236 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, 2>> querya[90][90];
vector <array<ll, 2>> possibledist[90][90];
ll dist[90], rdist[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) reachable[i][j] = -1;
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) dist[j] = 1e18, X[j] = -1;
    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]][query[i][1]].push_back({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) {
    for (auto [ti, limi, leni] : adj[i]) {
      for (int j=0; j<n; ++j) dist[j] = s, rdist[j] = -1e18;
      dist[i] = rdist[i] = limi;
      pq.push({limi, i, 0});
      while (!pq.empty()) {
        auto [w, u, t] = pq.top();
        pq.pop();
        if (dist[u] != w) continue;
        for (auto [v, lim, len] : adj[u]) {
          if (w <= lim && dist[v] > w+len) {
            dist[v] = w+len;
            pq.push({dist[v], v, 0});
          }
        }
      }
      rpq.push({limi, i});
      while (!rpq.empty()) {
        auto [w, u] = rpq.top();
        rpq.pop();
        if (rdist[u] != w) continue;
        for (auto [v, lim, len] : adj[u]) {
          if (rdist[v] < min(lim, w-len)) {
            rdist[v] = min(lim, w-len);
            rpq.push({rdist[v], v});
          }
        }
      }
      for (int x=0; x<n; ++x) {
        for (int y=0; y<n; ++y) {
          if (dist[y] >= s) continue;
          possibledist[x][y].push_back({rdist[x], dist[y]-rdist[x]});
        }
      }
    }
  }
  for (int i=0; i<n; ++i) {
    for (int j=0; j<n; ++j) {
      ll f = 1e18;
      sort(possibledist[i][j].begin(), possibledist[i][j].end());
      for (auto [t, id] : querya[i][j]) {
        while (!possibledist[i][j].empty() && t <= possibledist[i][j].back()[0]) {
          f = min(f, possibledist[i][j].back()[1]);
          possibledist[i][j].pop_back();
        }
        if (f == 1e18) F[id] = possibledist[i][j].back()[1];
        else F[id] = f;
      }
    }
  }
  return F;
}

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