Submission #1026916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026916		AdamGS	Escape Route (JOI21_escape_route)	C++17	5 / 100	9033 ms	164296 KiB

escape_route

#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=107;
pair<ll,ll>T[LIM][LIM];
vector<vector<ll>>X[LIM];
vector<ll>P[LIM], K[LIM];
ll n, S, q;
void calc1() {
  rep(i, n) {
    rep(j, n) P[i].pb(INF);
    vector<ll>odw(n);
    P[i][i]=0;
    while(true) {
      pair<ll,ll>mi={INF, INF};
      rep(j, n) if(!odw[j]) mi=min(mi, {P[i][j], j});
      if(mi.st==INF) break;
      ll p=mi.nd;
      odw[p]=1;
      rep(j, n) if(!odw[j] && T[p][j].nd!=-1) {
        ll a=mi.st/S, b=mi.st%S;
        if(b<=T[p][j].nd-T[p][j].st) P[i][j]=min(P[i][j], mi.st+T[p][j].st);
        else P[i][j]=min(P[i][j], (a+1)*S+T[p][j].st);
      }
    } 
  }
}
vector<ll>calc2(ll a, ll b) {
  vector<ll>odl(n, INF), odw(n);
  odl[a]=0;
  while(true) {
    pair<ll,ll>mi={INF, INF};
    rep(i, n) if(!odw[i]) mi=min(mi, {odl[i], i});
    if(mi.st==INF) break;
    ll p=mi.nd;
    odw[p]=1;
    rep(i, n) if(!odw[i] && T[p][i].nd!=-1) {
      if(mi.st+b<=T[p][i].nd-T[p][i].st) odl[i]=min(odl[i], mi.st+T[p][i].st);
    }
  }
  return odl;
}
void solve(ll x, ll l, ll r) {
  if(l==r) return;
  ll mid=(l+r+1)/2;
  vector<ll>A=calc2(x, l), B=calc2(x, mid), C=calc2(x, r);
  if(A!=B) {
    if(l+1==mid) {
      X[x].pb(B);
      K[x].pb(mid);
    } else solve(x, l, mid);
  }
  if(B!=C) solve(x, mid, r);
}
vector<ll>calculate_necessary_time(int _n, int _m, ll _S, int _q, vector<int>_A, vector<int>_B, 
    vector<ll>_L, vector<ll>_C, vector<int>_U, vector<int>_V, vector<ll>_T) {
  n=_n; S=_S; q=_q;
  rep(i, n) rep(j, n) T[i][j]={0, -1};
  rep(i, _m) T[_A[i]][_B[i]]=T[_B[i]][_A[i]]={_L[i], _C[i]};
  calc1();
  rep(i, n) {
    X[i].pb(calc2(i, 0));
    K[i].pb(0);
    solve(i, 0, S-1);
  }
  vector<ll>ans(q, INF);
  rep(i, q) {
    ll a=_U[i], b=_V[i], c=_T[i];
    ll po=0, ko=K[a].size()-1;
    while(po<ko) {
      ll sr=(po+ko+1)/2;
      if(K[a][sr]>c) ko=sr-1; else po=sr;
    }
    if(X[a][po][b]<INF) {
      ans[i]=X[a][po][b];
      continue;
    }
    rep(j, n) if(X[a][po][j]<INF) ans[i]=min(ans[i], S+P[j][b]-c);
  }
  return ans;
}

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