oj.uz

답안 #398809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398809 2021-05-04T20:30:24 Z fedoseevtimofey Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 196124 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) {
    vector <ll> die(2 * m, Linf);
    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) die[e.id] = min(die[e.id], t + delta);
        }
      }
    };

    recalc(0);

    int uk = 0;
    while (true) {
      int eid = -1;
      for (int i = 0; i < 2 * m; ++i) {
        if (kill[i]) continue;
        if (eid == -1 || die[i] < die[eid]) {
          eid = i;
        }
      }
      if (eid == -1) break;
      kill[eid] = 1;
      ll t = die[eid];
      if (t == prev_t) continue;
      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:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |       while (uk < qs[st].size() && T[qs[st][uk]] < t) {
      |              ~~~^~~~~~~~~~~~~~~
escape_route.cpp:143:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     while (uk < qs[st].size()) {
      |            ~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 64 ms 64964 KB Output is correct
3 Correct 1211 ms 64976 KB Output is correct
4 Correct 27 ms 64956 KB Output is correct
5 Correct 37 ms 65012 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2564 ms 112284 KB Output is correct
2 Correct 2650 ms 122340 KB Output is correct
3 Correct 2700 ms 113388 KB Output is correct
4 Correct 2647 ms 123404 KB Output is correct
5 Correct 2700 ms 123476 KB Output is correct
6 Correct 31 ms 64948 KB Output is correct
7 Correct 2852 ms 113408 KB Output is correct
8 Correct 2862 ms 136004 KB Output is correct
9 Correct 2617 ms 113152 KB Output is correct
10 Correct 2732 ms 122584 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 64 ms 64964 KB Output is correct
3 Correct 1211 ms 64976 KB Output is correct
4 Correct 27 ms 64956 KB Output is correct
5 Correct 37 ms 65012 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 2564 ms 112284 KB Output is correct
8 Correct 2650 ms 122340 KB Output is correct
9 Correct 2700 ms 113388 KB Output is correct
10 Correct 2647 ms 123404 KB Output is correct
11 Correct 2700 ms 123476 KB Output is correct
12 Correct 31 ms 64948 KB Output is correct
13 Correct 2852 ms 113408 KB Output is correct
14 Correct 2862 ms 136004 KB Output is correct
15 Correct 2617 ms 113152 KB Output is correct
16 Correct 2732 ms 122584 KB Output is correct
17 Correct 3690 ms 112708 KB Output is correct
18 Correct 3618 ms 156792 KB Output is correct
19 Correct 3734 ms 175296 KB Output is correct
20 Correct 3748 ms 156484 KB Output is correct
21 Correct 3670 ms 184524 KB Output is correct
22 Correct 3863 ms 183384 KB Output is correct
23 Correct 3870 ms 157124 KB Output is correct
24 Correct 2766 ms 196124 KB Output is correct
25 Correct 3831 ms 157064 KB Output is correct
26 Correct 3817 ms 184428 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 64 ms 64964 KB Output is correct
3 Correct 1211 ms 64976 KB Output is correct
4 Correct 27 ms 64956 KB Output is correct
5 Correct 37 ms 65012 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 2564 ms 112284 KB Output is correct
8 Correct 2650 ms 122340 KB Output is correct
9 Correct 2700 ms 113388 KB Output is correct
10 Correct 2647 ms 123404 KB Output is correct
11 Correct 2700 ms 123476 KB Output is correct
12 Correct 31 ms 64948 KB Output is correct
13 Correct 2852 ms 113408 KB Output is correct
14 Correct 2862 ms 136004 KB Output is correct
15 Correct 2617 ms 113152 KB Output is correct
16 Correct 2732 ms 122584 KB Output is correct
17 Correct 3690 ms 112708 KB Output is correct
18 Correct 3618 ms 156792 KB Output is correct
19 Correct 3734 ms 175296 KB Output is correct
20 Correct 3748 ms 156484 KB Output is correct
21 Correct 3670 ms 184524 KB Output is correct
22 Correct 3863 ms 183384 KB Output is correct
23 Correct 3870 ms 157124 KB Output is correct
24 Correct 2766 ms 196124 KB Output is correct
25 Correct 3831 ms 157064 KB Output is correct
26 Correct 3817 ms 184428 KB Output is correct
27 Execution timed out 9071 ms 157584 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 64 ms 64964 KB Output is correct
3 Correct 1211 ms 64976 KB Output is correct
4 Correct 27 ms 64956 KB Output is correct
5 Correct 37 ms 65012 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 2564 ms 112284 KB Output is correct
8 Correct 2650 ms 122340 KB Output is correct
9 Correct 2700 ms 113388 KB Output is correct
10 Correct 2647 ms 123404 KB Output is correct
11 Correct 2700 ms 123476 KB Output is correct
12 Correct 31 ms 64948 KB Output is correct
13 Correct 2852 ms 113408 KB Output is correct
14 Correct 2862 ms 136004 KB Output is correct
15 Correct 2617 ms 113152 KB Output is correct
16 Correct 2732 ms 122584 KB Output is correct
17 Correct 3690 ms 112708 KB Output is correct
18 Correct 3618 ms 156792 KB Output is correct
19 Correct 3734 ms 175296 KB Output is correct
20 Correct 3748 ms 156484 KB Output is correct
21 Correct 3670 ms 184524 KB Output is correct
22 Correct 3863 ms 183384 KB Output is correct
23 Correct 3870 ms 157124 KB Output is correct
24 Correct 2766 ms 196124 KB Output is correct
25 Correct 3831 ms 157064 KB Output is correct
26 Correct 3817 ms 184428 KB Output is correct
27 Execution timed out 9071 ms 157584 KB Time limit exceeded
28 Halted 0 ms 0 KB -