oj.uz

Submission #1026899

# Submission time Handle Problem Language Result Execution time Memory
1026899 2024-07-18T13:17:58 Z AdamGS Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 155316 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<ll>P[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]=b;
  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<=T[p][i].nd-T[p][i].st) odl[i]=min(odl[i], mi.st+T[p][i].st);
    }
  }
  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();
  vector<ll>ans(q, INF);
  rep(i, q) {
    ll a=_U[i], b=_V[i], c=_T[i];
    vector<ll>A=calc2(a, c);
    if(A[b]<INF) {
      ans[i]=A[b]-c;
      continue;
    }
    rep(j, n) if(A[j]<INF) ans[i]=min(ans[i], S+P[j][b]-c);
  }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 18 ms 65228 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9071 ms 155316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 18 ms 65228 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Execution timed out 9071 ms 155316 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 18 ms 65228 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Execution timed out 9071 ms 155316 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 12 ms 65116 KB Output is correct
3 Correct 18 ms 65228 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Execution timed out 9071 ms 155316 KB Time limit exceeded
8 Halted 0 ms 0 KB -