Submission #1157686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157686		adiyer	Escape Route (JOI21_escape_route)	C++20	5 / 100	9090 ms	112180 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;

typedef long long ll;
typedef double ld;

const int N = 1e2 + 11;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, m, s, q;
ll d[N];

vector < ll > ans;

vector < array < ll, 3 > > g[N];

vector < ll > calculate_necessary_time(int N, int M, long long 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, m = M, s = S, q = Q;
  for(ll i = 0; i < m; i++){
    g[A[i]].pb({B[i], L[i], C[i]});
    g[B[i]].pb({A[i], L[i], C[i]});
  }
  for(ll i = 0; i < q; i++){
    ll st = U[i], fn = V[i], t = T[i];
    for(ll i = 0; i < n; i++) d[i] = inf;
    set < pair < ll, ll > > q;
    d[st] = t, q.insert({d[st], st});
    while(len(q)){
      ll v = (q.begin() -> S);
      q.erase(q.begin());
      for(array < ll, 3 > cur : g[v]){
        ll u = cur[0], w = cur[1], c = cur[2];
        if(d[v] + w <= c + d[v] / s * s && d[v] + w < d[u]){
          q.erase({d[u], u});
          d[u] = d[v] + w;
          q.insert({d[u], u});
        }
        if((d[v] + s - 1) / s * s + w < d[u]){
          q.erase({d[u], u});
          d[u] = (d[v] + s - 1) / s * s + w;
          q.insert({d[u], u});
        }
      }
    }
    ans.pb(d[fn] - t);
  }
  return ans;
}

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