oj.uz

Submission #417593

# Submission time Handle Problem Language Result Execution time Memory
417593 2021-06-04T02:19:06 Z Mamnoon_Siam Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 160668 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define sz(v) (int)(v.size())

#define INPUT "sample-01-in.txt"

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(...)
#endif

namespace {

  const ll inf = 1e18;
  template <typename T>
  inline void chkmin(T& x, T y) {
    x = x < y ? x : y;
  }

  int N, M, Q;
  ll S;
  vi A, B;
  vll L, C, T;
  vi U, V;

  ll roundup(ll x) {
    ll r = x % S;
    x += r ? S - r : 0;
    return x;
  }

  ll solve(int u, int v, ll t) {
    vll dis(N, inf);
    dis[u] = t;
    for(int it = 1; it < N+10; ++it) {
      for(int i = 0; i < M; ++i) {
        int a = A[i], b = B[i];
        ll c = C[i], l = L[i];
        for(int j : {0, 1}) {
          if(dis[a] % S <= c - l) {
            chkmin(dis[b], dis[a] + l);
          } else {
            chkmin(dis[b], roundup(dis[a]) + l);
          }
          swap(a, b);
        }
      }
    }
    return dis[v];
  }

}

vll calculate_necessary_time(
    int N, int M, ll S, int Q, vi A, vi B,
    vll L, vll C, vi U,
    vi V, vll T) {
  ::N = N, ::M = M, :: S = S, ::Q = Q, ::A = A, ::B = B;
  ::L = L, ::C = C, ::U = U, ::V = V, ::T = T;
  vll ans(Q);
  for(int i = 0 ; i < Q; ++i) {
    ans[i] = solve(U[i], V[i], T[i]) - T[i];
  }
  return ans;
}

#ifdef LOCAL
#include <unistd.h>

namespace grader {
const int N_MAX = 90;
const int M_MAX = N_MAX * (N_MAX - 1) / 2;
const long long S_MAX = 1000000000000000;
const int Q_MAX = 3000000;

int digits(long long x) {
  if (x < 10) {
    return 1;
  }
  return digits(x / 10) + 1;
}

const int N_digits = digits(N_MAX);
const int M_digits = digits(M_MAX);
const int S_digits = digits(S_MAX);
const int Q_digits = digits(Q_MAX);
const int ABUV_digits = digits(N_MAX - 1);
const int LCT_digits = digits(S_MAX - 1);
const int answer_digits = 19;

int N, M, Q;
long long S;
std::vector<int> A, B, U, V;
std::vector<long long> L, C, T;

class Input {
 private:
  std::vector<char> buffer;
  int pos;

  int read_NABUV() {
    if (buffer[pos + 1] == ' ') {
      int x = buffer[pos] - '0';
      pos += 2;
      return x;
    } else {
      int x = (buffer[pos] - '0') * 10 + (buffer[pos + 1] - '0');
      pos += 3;
      return x;
    }
  }
  long long read_number(char sep) {
    long long x = 0;
    while (true) {
      if (buffer[pos] == sep) {
        pos++;
        break;
      } else if (buffer[pos + 1] == sep) {
        x = x * 10 + (long long)(buffer[pos] - '0');
        pos += 2;
        break;
      } else {
        x = x * 100 +
            (long long)((buffer[pos] - '0') * 10 + (buffer[pos + 1] - '0'));
        pos += 2;
      }
    }
    return x;
  }

 public:
  void read_all() {
    int l1 = N_digits + 1 + M_digits + 1 + S_digits + 1 + Q_digits + 1;
    int l2 =
        (ABUV_digits + 1 + ABUV_digits + 1 + LCT_digits + 1 + LCT_digits + 1) *
        M_MAX;
    int l3 = (ABUV_digits + 1 + ABUV_digits + 1 + LCT_digits + 1) * Q_MAX;
    int total_length = l1 + l2 + l3;
    buffer.resize(total_length + 1);
    size_t read_result =
        read(0, buffer.data(), sizeof(char) * (total_length + 1));
    assert(read_result <= sizeof(char) * (total_length + 1));
    pos = 0;

    N = read_NABUV();
    M = read_number(' ');
    S = read_number(' ');
    Q = read_number('\n');

    A.resize(M);
    B.resize(M);
    L.resize(M);
    C.resize(M);
    for (int i = 0; i < M; i++) {
      A[i] = read_NABUV();
      B[i] = read_NABUV();
      L[i] = read_number(' ');
      C[i] = read_number('\n');
    }

    U.resize(Q);
    V.resize(Q);
    T.resize(Q);
    for (int j = 0; j < Q; j++) {
      U[j] = read_NABUV();
      V[j] = read_NABUV();
      T[j] = read_number('\n');
    }
  }
};

void output(std::vector<long long>& answer) {
  int total_length = (answer_digits + 1) * answer.size();
  std::vector<char> buffer(total_length);
  int pos = 0;

  std::vector<char> tmp(answer_digits);
  for (long long ans : answer) {
    int p2 = answer_digits - 1;
    while (true) {
      if (ans < 10) {
        tmp[p2] = char(ans) + '0';
        break;
      }
      tmp[p2] = char(ans % 10) + '0';
      ans /= 10;
      p2--;
    }
    memcpy(buffer.data() + pos, tmp.data() + p2, answer_digits - p2);
    pos += answer_digits - p2;
    buffer[pos] = '\n';
    pos++;
  }

  int write_result = write(1, buffer.data(), sizeof(char) * pos);
  assert(write_result == pos);
}

void main() {
  Input().read_all();

  std::vector<long long> answer = calculate_necessary_time(
      N, M, S, Q, std::move(A), std::move(B), std::move(L), std::move(C),
      std::move(U), std::move(V), std::move(T));
  assert(answer.size() == (size_t)Q);

  output(answer);
}

}  // namespace

int main(int argc, char const *argv[])
{
  freopen(INPUT, "r", stdin);
  grader::main();
  return 0;
}
#endif

Compilation message

escape_route.cpp: In function 'll {anonymous}::solve(int, int, ll)':
escape_route.cpp:49:17: warning: unused variable 'j' [-Wunused-variable]
   49 |         for(int j : {0, 1}) {
      |                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64972 KB Output is correct
2 Correct 170 ms 64932 KB Output is correct
3 Correct 555 ms 65084 KB Output is correct
4 Correct 27 ms 64968 KB Output is correct
5 Correct 499 ms 65028 KB Output is correct
6 Correct 57 ms 65048 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64972 KB Output is correct
2 Correct 170 ms 64932 KB Output is correct
3 Correct 555 ms 65084 KB Output is correct
4 Correct 27 ms 64968 KB Output is correct
5 Correct 499 ms 65028 KB Output is correct
6 Correct 57 ms 65048 KB Output is correct
7 Execution timed out 9032 ms 160668 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64972 KB Output is correct
2 Correct 170 ms 64932 KB Output is correct
3 Correct 555 ms 65084 KB Output is correct
4 Correct 27 ms 64968 KB Output is correct
5 Correct 499 ms 65028 KB Output is correct
6 Correct 57 ms 65048 KB Output is correct
7 Execution timed out 9032 ms 160668 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64972 KB Output is correct
2 Correct 170 ms 64932 KB Output is correct
3 Correct 555 ms 65084 KB Output is correct
4 Correct 27 ms 64968 KB Output is correct
5 Correct 499 ms 65028 KB Output is correct
6 Correct 57 ms 65048 KB Output is correct
7 Execution timed out 9032 ms 160668 KB Time limit exceeded
8 Halted 0 ms 0 KB -