oj.uz

Submission #398744

# Submission time Handle Problem Language Result Execution time Memory
398744 2021-05-04T19:15:02 Z fedoseevtimofey Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 154876 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>

using namespace std;
 
typedef long long ll;

#include "escape_route.h"

struct Edge {
  int u, v; ll l, c;
};

const int Inf = 1e9;
const ll Linf = 1e18;

std::vector<long long> calculate_necessary_time(int n, int m, long long s, int q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) {
  vector <vector <Edge>> g(n);
  for (int i = 0; i < m; ++i) {
    g[A[i]].push_back({A[i], B[i], L[i], C[i]});
    g[B[i]].push_back({B[i], A[i], L[i], C[i]});
  }
  vector <ll> ans(q);
  for (int t = 0; t < q; ++t) {
    vector <ll> d(n, Linf);
    d[U[t]] = T[t];
    set <pair <ll, int>> q;
    q.insert({d[U[t]], U[t]});
    while (!q.empty()) {
      int u = q.begin()->second;
      q.erase(q.begin());
      ll tm = d[u] % s;
      for (auto e : g[u]) {
        ll dist = d[u];
        if (tm > e.c - e.l) {
          dist += s - tm;
        }
        dist += e.l;
        if (dist < d[e.v]) {
          q.erase({d[e.v], e.v});
          d[e.v] = dist;
          q.insert({d[e.v], e.v});
        }
      }
    }
    ans[t] = d[V[t]] - d[U[t]];
  }
  return ans;
}

#ifdef LOCAL
#include <unistd.h>
#include <cassert>
#include <cstring>
namespace {
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);
}
}  // namespace

int main() {
  freopen("input.txt", "r", stdin);
  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);
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64964 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 59 ms 64996 KB Output is correct
4 Correct 28 ms 64952 KB Output is correct
5 Correct 36 ms 65040 KB Output is correct
6 Correct 32 ms 64972 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64964 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 59 ms 64996 KB Output is correct
4 Correct 28 ms 64952 KB Output is correct
5 Correct 36 ms 65040 KB Output is correct
6 Correct 32 ms 64972 KB Output is correct
7 Execution timed out 9006 ms 154876 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64964 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 59 ms 64996 KB Output is correct
4 Correct 28 ms 64952 KB Output is correct
5 Correct 36 ms 65040 KB Output is correct
6 Correct 32 ms 64972 KB Output is correct
7 Execution timed out 9006 ms 154876 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64964 KB Output is correct
2 Correct 44 ms 64972 KB Output is correct
3 Correct 59 ms 64996 KB Output is correct
4 Correct 28 ms 64952 KB Output is correct
5 Correct 36 ms 65040 KB Output is correct
6 Correct 32 ms 64972 KB Output is correct
7 Execution timed out 9006 ms 154876 KB Time limit exceeded
8 Halted 0 ms 0 KB -