Submission #398798

#	Time	Username	Problem	Language	Result	Execution time	Memory
398798		fedoseevtimofey	Escape Route (JOI21_escape_route)	C++17	25 / 100	9043 ms	194004 KiB

escape_route

#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, id; 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], 2 * i, L[i], C[i]});
    g[B[i]].push_back({B[i], A[i], 2 * i + 1, L[i], C[i]});
  }
  vector <vector <ll>> cd(n, vector <ll> (n, Linf));
  for (int st = 0; st < n; ++st) {
    auto &d = cd[st];
    d[st] = 0;
    set <pair <ll, int>> q;
    q.insert({d[st], st});
    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});
        }
      }
    }
  }
  vector <vector <int>> qs(n);
  for (int i = 0; i < q; ++i) {
    qs[U[i]].push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    sort(qs[i].begin(), qs[i].end(), [&] (int f, int s) {
      return T[f] < T[s];
    });
  }
  vector <ll> ans(q, Linf);
  for (int st = 0; st < n; ++st) {
    set <pair <ll, int>> ev;
    vector <int> kill(2 * 2 * m);
    vector <ll> d(n, Linf);
    ll prev_t = -1;
    auto recalc = [&] (ll t) {
      prev_t = t;
      d.assign(n, Linf);
      d[st] = t;
      vector <int> used(n);
      for (int it = 0; it < n; ++it) {
        int u = -1;
        for (int i = 0; i < n; ++i) {
          if (used[i]) continue;
          if (u == -1 || d[i] < d[u]) {
            u = i;
          }
        }
        if (u == -1) break;
        used[u] = 1;
        ll tm = d[u] % s;
        for (auto e : g[u]) {
          ll dist = d[u];
          if (tm > e.c - e.l) {
            continue;
          }
          dist += e.l;
          d[e.v] = min(d[e.v], dist);
        }
      }
      for (int u = 0; u < n; ++u) {
        for (auto e : g[u]) {
          if (kill[e.id]) continue;
           //d[u] + delta + l > e.c
           //delta > e.c - d[u] - l
          ll delta = e.c - d[u] - e.l + 1;
          if (delta > 0) ev.insert({t + delta, e.id});
        }
      }
    };
    int uk = 0;
    ev.insert({0, -1});
    while (!ev.empty()) {
      auto p = *ev.begin();
      ev.erase(ev.begin());
      if (p.second != -1 && kill[p.second]) continue;
      if (p.second != -1) kill[p.second] = 1;
      ll t = p.first;

      while (uk < qs[st].size() && T[qs[st][uk]] < t) {
        int id = qs[st][uk];
        ans[id] = min(ans[id], d[V[id]] - prev_t);
        for (int u = 0; u < n; ++u) {
          ans[id] = min(ans[id], d[u] - prev_t + (s - (d[u] - prev_t + T[id]) % s) % s + cd[u][V[id]]);
        }
        ++uk;
      }
      if (uk == (int)qs[st].size()) break;
      recalc(t);
    }
    while (uk < qs[st].size()) {
      int id = qs[st][uk];
      ans[id] = min(ans[id], d[V[id]] - prev_t);
      for (int u = 0; u < n; ++u) {
        ans[id] = min(ans[id], d[u] - prev_t + (s - (d[u] - prev_t + T[id]) % s) % s + cd[u][V[id]]);
      }
      ++uk;
    }
  }
  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

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, 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:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |       while (uk < qs[st].size() && T[qs[st][uk]] < t) {
      |              ~~~^~~~~~~~~~~~~~~
escape_route.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     while (uk < qs[st].size()) {
      |            ~~~^~~~~~~~~~~~~~~

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