Submission #1028944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028944		AdamGS	Escape Route (JOI21_escape_route)	C++17	20 / 100	829 ms	194572 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 li[LIM], 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);
    rep(j, X[i].size()) {
      rep(l, n) if(X[i][j][l]==INF) X[i][j][l]=2*INF;
      rep(l, n) if(X[i][j][l]<INF) {
        rep(d, n) X[i][j][d]=min(X[i][j][d], INF+S+P[l][d]);
      }
    }
    break;
  }
  vector<ll>ans(q, INF);
  vector<pair<ll,ll>>pyt(q);
  rep(i, q) pyt[i]={_T[i], i};
  sort(all(pyt));
  for(auto xd : pyt) {
    int i=xd.nd;
    ll a=_U[i], b=_V[i], c=_T[i];
    while(li[a]+1<K[a].size() && K[a][li[a]+1]<=c) {
      ++li[a];
    }
    ll po=li[a];
    if(X[a][po][b]<INF) {
      ans[i]=X[a][po][b];
      continue;
    }
    ans[i]=X[a][po][b]-INF-c;
  }
  return ans;
}

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, ll, 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:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
escape_route.cpp:72:5: note: in expansion of macro 'rep'
   72 |     rep(j, X[i].size()) {
      |     ^~~
escape_route.cpp:87:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     while(li[a]+1<K[a].size() && K[a][li[a]+1]<=c) {
      |           ~~~~~~~^~~~~~~~~~~~

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