oj.uz

Submission #398798

# Submission time Handle Problem Language Result Execution time Memory
398798 2021-05-04T20:19:25 Z fedoseevtimofey Escape Route (JOI21_escape_route) C++17
25 / 100
 9000 ms 194004 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, 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64996 KB Output is correct
2 Correct 70 ms 65036 KB Output is correct
3 Correct 5115 ms 65040 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 48 ms 64964 KB Output is correct
6 Correct 29 ms 65052 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 112804 KB Output is correct
2 Correct 3205 ms 179412 KB Output is correct
3 Correct 2873 ms 153640 KB Output is correct
4 Correct 3086 ms 188860 KB Output is correct
5 Correct 3077 ms 188800 KB Output is correct
6 Correct 27 ms 64964 KB Output is correct
7 Correct 2852 ms 155000 KB Output is correct
8 Correct 2942 ms 194004 KB Output is correct
9 Correct 3047 ms 154960 KB Output is correct
10 Correct 3187 ms 188336 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64996 KB Output is correct
2 Correct 70 ms 65036 KB Output is correct
3 Correct 5115 ms 65040 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 48 ms 64964 KB Output is correct
6 Correct 29 ms 65052 KB Output is correct
7 Correct 2882 ms 112804 KB Output is correct
8 Correct 3205 ms 179412 KB Output is correct
9 Correct 2873 ms 153640 KB Output is correct
10 Correct 3086 ms 188860 KB Output is correct
11 Correct 3077 ms 188800 KB Output is correct
12 Correct 27 ms 64964 KB Output is correct
13 Correct 2852 ms 155000 KB Output is correct
14 Correct 2942 ms 194004 KB Output is correct
15 Correct 3047 ms 154960 KB Output is correct
16 Correct 3187 ms 188336 KB Output is correct
17 Execution timed out 9043 ms 156780 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64996 KB Output is correct
2 Correct 70 ms 65036 KB Output is correct
3 Correct 5115 ms 65040 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 48 ms 64964 KB Output is correct
6 Correct 29 ms 65052 KB Output is correct
7 Correct 2882 ms 112804 KB Output is correct
8 Correct 3205 ms 179412 KB Output is correct
9 Correct 2873 ms 153640 KB Output is correct
10 Correct 3086 ms 188860 KB Output is correct
11 Correct 3077 ms 188800 KB Output is correct
12 Correct 27 ms 64964 KB Output is correct
13 Correct 2852 ms 155000 KB Output is correct
14 Correct 2942 ms 194004 KB Output is correct
15 Correct 3047 ms 154960 KB Output is correct
16 Correct 3187 ms 188336 KB Output is correct
17 Execution timed out 9043 ms 156780 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64996 KB Output is correct
2 Correct 70 ms 65036 KB Output is correct
3 Correct 5115 ms 65040 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 48 ms 64964 KB Output is correct
6 Correct 29 ms 65052 KB Output is correct
7 Correct 2882 ms 112804 KB Output is correct
8 Correct 3205 ms 179412 KB Output is correct
9 Correct 2873 ms 153640 KB Output is correct
10 Correct 3086 ms 188860 KB Output is correct
11 Correct 3077 ms 188800 KB Output is correct
12 Correct 27 ms 64964 KB Output is correct
13 Correct 2852 ms 155000 KB Output is correct
14 Correct 2942 ms 194004 KB Output is correct
15 Correct 3047 ms 154960 KB Output is correct
16 Correct 3187 ms 188336 KB Output is correct
17 Execution timed out 9043 ms 156780 KB Time limit exceeded
18 Halted 0 ms 0 KB -