oj.uz

Submission #1029014

# Submission time Handle Problem Language Result Execution time Memory
1029014 2024-07-20T11:18:00 Z AdamGS Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 346384 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], lst;
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) {
  lst.clear();
  rep(i, n) lst.pb(-1);
  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) {
        if(mi.st+T[p][i].st<odl[i]) {
          odl[i]=mi.st+T[p][i].st;
          lst[i]=p;
        }
      }
    }
  }
  return odl;
}
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);
    while(true) {
      ll s=K[i].size()-1, nxt=INF;
      rep(j, n) if(lst[j]!=-1) {
        nxt=min(nxt, T[lst[j]][j].nd-T[lst[j]][j].st-X[i][s][lst[j]]-K[i][s]);
      }
      nxt+=K[i][s]+1;
      if(nxt>=INF) break;
      X[i].pb(calc2(i, nxt));
      K[i].pb(nxt);
    }
    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);
  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

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:76:5: note: in expansion of macro 'rep'
   76 |     rep(j, X[i].size()) {
      |     ^~~
escape_route.cpp:90: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]
   90 |     while(li[a]+1<K[a].size() && K[a][li[a]+1]<=c) {
      |           ~~~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65112 KB Output is correct
2 Correct 26 ms 65116 KB Output is correct
3 Correct 49 ms 65112 KB Output is correct
4 Correct 19 ms 64996 KB Output is correct
5 Correct 20 ms 65104 KB Output is correct
6 Correct 20 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 167832 KB Output is correct
2 Correct 739 ms 180236 KB Output is correct
3 Correct 559 ms 158572 KB Output is correct
4 Correct 719 ms 189024 KB Output is correct
5 Correct 754 ms 189088 KB Output is correct
6 Correct 21 ms 65104 KB Output is correct
7 Correct 578 ms 160152 KB Output is correct
8 Correct 564 ms 191320 KB Output is correct
9 Correct 633 ms 165840 KB Output is correct
10 Correct 718 ms 188712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65112 KB Output is correct
2 Correct 26 ms 65116 KB Output is correct
3 Correct 49 ms 65112 KB Output is correct
4 Correct 19 ms 64996 KB Output is correct
5 Correct 20 ms 65104 KB Output is correct
6 Correct 20 ms 65116 KB Output is correct
7 Correct 682 ms 167832 KB Output is correct
8 Correct 739 ms 180236 KB Output is correct
9 Correct 559 ms 158572 KB Output is correct
10 Correct 719 ms 189024 KB Output is correct
11 Correct 754 ms 189088 KB Output is correct
12 Correct 21 ms 65104 KB Output is correct
13 Correct 578 ms 160152 KB Output is correct
14 Correct 564 ms 191320 KB Output is correct
15 Correct 633 ms 165840 KB Output is correct
16 Correct 718 ms 188712 KB Output is correct
17 Correct 688 ms 168812 KB Output is correct
18 Correct 688 ms 169720 KB Output is correct
19 Correct 664 ms 182548 KB Output is correct
20 Correct 562 ms 158880 KB Output is correct
21 Correct 758 ms 187176 KB Output is correct
22 Correct 703 ms 191340 KB Output is correct
23 Correct 537 ms 162204 KB Output is correct
24 Correct 571 ms 193000 KB Output is correct
25 Correct 616 ms 167764 KB Output is correct
26 Correct 753 ms 191492 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65112 KB Output is correct
2 Correct 26 ms 65116 KB Output is correct
3 Correct 49 ms 65112 KB Output is correct
4 Correct 19 ms 64996 KB Output is correct
5 Correct 20 ms 65104 KB Output is correct
6 Correct 20 ms 65116 KB Output is correct
7 Correct 682 ms 167832 KB Output is correct
8 Correct 739 ms 180236 KB Output is correct
9 Correct 559 ms 158572 KB Output is correct
10 Correct 719 ms 189024 KB Output is correct
11 Correct 754 ms 189088 KB Output is correct
12 Correct 21 ms 65104 KB Output is correct
13 Correct 578 ms 160152 KB Output is correct
14 Correct 564 ms 191320 KB Output is correct
15 Correct 633 ms 165840 KB Output is correct
16 Correct 718 ms 188712 KB Output is correct
17 Correct 688 ms 168812 KB Output is correct
18 Correct 688 ms 169720 KB Output is correct
19 Correct 664 ms 182548 KB Output is correct
20 Correct 562 ms 158880 KB Output is correct
21 Correct 758 ms 187176 KB Output is correct
22 Correct 703 ms 191340 KB Output is correct
23 Correct 537 ms 162204 KB Output is correct
24 Correct 571 ms 193000 KB Output is correct
25 Correct 616 ms 167764 KB Output is correct
26 Correct 753 ms 191492 KB Output is correct
27 Correct 1428 ms 197844 KB Output is correct
28 Correct 1495 ms 202468 KB Output is correct
29 Correct 1636 ms 218156 KB Output is correct
30 Correct 601 ms 162440 KB Output is correct
31 Correct 1618 ms 226252 KB Output is correct
32 Correct 1640 ms 226076 KB Output is correct
33 Correct 560 ms 193636 KB Output is correct
34 Correct 1305 ms 194600 KB Output is correct
35 Correct 1580 ms 225280 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65112 KB Output is correct
2 Correct 26 ms 65116 KB Output is correct
3 Correct 49 ms 65112 KB Output is correct
4 Correct 19 ms 64996 KB Output is correct
5 Correct 20 ms 65104 KB Output is correct
6 Correct 20 ms 65116 KB Output is correct
7 Correct 682 ms 167832 KB Output is correct
8 Correct 739 ms 180236 KB Output is correct
9 Correct 559 ms 158572 KB Output is correct
10 Correct 719 ms 189024 KB Output is correct
11 Correct 754 ms 189088 KB Output is correct
12 Correct 21 ms 65104 KB Output is correct
13 Correct 578 ms 160152 KB Output is correct
14 Correct 564 ms 191320 KB Output is correct
15 Correct 633 ms 165840 KB Output is correct
16 Correct 718 ms 188712 KB Output is correct
17 Correct 688 ms 168812 KB Output is correct
18 Correct 688 ms 169720 KB Output is correct
19 Correct 664 ms 182548 KB Output is correct
20 Correct 562 ms 158880 KB Output is correct
21 Correct 758 ms 187176 KB Output is correct
22 Correct 703 ms 191340 KB Output is correct
23 Correct 537 ms 162204 KB Output is correct
24 Correct 571 ms 193000 KB Output is correct
25 Correct 616 ms 167764 KB Output is correct
26 Correct 753 ms 191492 KB Output is correct
27 Correct 1428 ms 197844 KB Output is correct
28 Correct 1495 ms 202468 KB Output is correct
29 Correct 1636 ms 218156 KB Output is correct
30 Correct 601 ms 162440 KB Output is correct
31 Correct 1618 ms 226252 KB Output is correct
32 Correct 1640 ms 226076 KB Output is correct
33 Correct 560 ms 193636 KB Output is correct
34 Correct 1305 ms 194600 KB Output is correct
35 Correct 1580 ms 225280 KB Output is correct
36 Correct 7202 ms 332216 KB Output is correct
37 Correct 8631 ms 346384 KB Output is correct
38 Correct 998 ms 180196 KB Output is correct
39 Execution timed out 9062 ms 340524 KB Time limit exceeded
40 Halted 0 ms 0 KB -