oj.uz

Submission #1026920

# Submission time Handle Problem Language Result Execution time Memory
1026920 2024-07-18T13:48:30 Z AdamGS Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 115340 KB 
#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);
    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]);
      }
    }
  }
  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;
    }
    ans[i]=X[a][po][b]-INF-c;
  }
  return ans;
}

Compilation message

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()) {
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 65112 KB Output is correct
2 Correct 265 ms 65116 KB Output is correct
3 Correct 2214 ms 65112 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 8 ms 65116 KB Output is correct
6 Correct 14 ms 65036 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6648 ms 115340 KB Output is correct
2 Execution timed out 9026 ms 111952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 65112 KB Output is correct
2 Correct 265 ms 65116 KB Output is correct
3 Correct 2214 ms 65112 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 8 ms 65116 KB Output is correct
6 Correct 14 ms 65036 KB Output is correct
7 Correct 6648 ms 115340 KB Output is correct
8 Execution timed out 9026 ms 111952 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 65112 KB Output is correct
2 Correct 265 ms 65116 KB Output is correct
3 Correct 2214 ms 65112 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 8 ms 65116 KB Output is correct
6 Correct 14 ms 65036 KB Output is correct
7 Correct 6648 ms 115340 KB Output is correct
8 Execution timed out 9026 ms 111952 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 65112 KB Output is correct
2 Correct 265 ms 65116 KB Output is correct
3 Correct 2214 ms 65112 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 8 ms 65116 KB Output is correct
6 Correct 14 ms 65036 KB Output is correct
7 Correct 6648 ms 115340 KB Output is correct
8 Execution timed out 9026 ms 111952 KB Time limit exceeded
9 Halted 0 ms 0 KB -