Submission #752579

#	Time	Username	Problem	Language	Result	Execution time	Memory
752579		tch1cherin	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	985 ms	158572 KiB

ho_t4

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
 
const int N = 200, M = 50000;
vector<int> graph[2][N];
int deg[N], rev_deg[N], path[N], dist[N], _from[M], _to[M], weight[M], cost[M];
int dist_w[4][M][N], dist_i[4][N];
int n, m;
 
int from(int g, int id) {
  return g == 0 ? _from[id] : _to[id];
}
 
int to(int g, int id) {
  return g == 0 ? _to[id] : _from[id];
}
 
void dijkstra(int start, int g, bool flag, int del = -1) {
  fill(dist, dist + n, INT_MAX);
  if (flag) fill(path, path + n, -1);
  dist[start] = 0;
  struct P {
      int t;
      int v;
      bool operator>(const P& x) const {
          return t == x.t ? v > x.v : t > x.t;
      }
      P(int _t, int _v) : t(_t), v(_v) {}
  };
  priority_queue<P, vector<P>, greater<P>> q;
  q.emplace(0, start);
  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();
    if (dist[u] > d) {
      continue;
    }
    for (int e : graph[g][u]) {
      if (e != del && dist[u] + weight[e] < dist[to(g, e)]) {
        dist[to(g, e)] = dist[u] + weight[e];
        if (flag) path[to(g, e)] = e;
        q.emplace(dist[to(g, e)], to(g, e));
      }
    }
  }
}

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

void _solve(int g, int start, int it) {
  dijkstra(start, g, true);
  memcpy(dist_i[it], dist, sizeof dist);
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  shuffle(order.begin(), order.end(), rng);
  for (int i : order) {
    if (path[i] != -1) {
      dijkstra(start, g, false, path[i]);
      memcpy(dist_w[it][path[i]], dist, sizeof dist);
      if (1.0 * clock() / CLOCKS_PER_SEC >= 0.95) {
        return;
      }
    }
  }
}
 
int Get(int it, int id, int u) {
  return dist_w[it][id][u] == -1 ? dist_i[it][u] : dist_w[it][id][u];
}
 
void solve() {
  cin >> n >> m;
  memset(dist_w, -1, sizeof dist_w);
  for (int i = 0; i < m; i++) {
    cin >> _from[i] >> _to[i] >> weight[i] >> cost[i];
    _from[i]--, _to[i]--;
    deg[_from[i]]++, rev_deg[_to[i]]++;
  }
  for (int i = 0; i < n; i++) {
    graph[0][i].reserve(deg[i]);
    graph[1][i].reserve(rev_deg[i]);
  }
  for (int i = 0; i < m; i++) {
    graph[0][_from[i]].push_back(i);
    graph[1][_to[i]].push_back(i);
  }
  _solve(0, 0, 0);
  _solve(0, n - 1, 1);
  _solve(1, 0, 2);
  _solve(1, n - 1, 3);
  int ans = INT_MAX;
  if (dist_i[0][n - 1] != INT_MAX && dist_i[1][0] != INT_MAX) {
    ans = dist_i[0][n - 1] + dist_i[1][0];
  }
  for (int u = 0; u < n; u++) {
    for (int id : graph[0][u]) {
      int AB = INT_MAX, BA = INT_MAX;
      AB = min(AB, Get(0, id, n - 1));
      if (Get(0, id, to(0, id)) != INT_MAX && Get(3, id, from(0, id)) != INT_MAX) {
        AB = min(AB, Get(0, id, to(0, id)) + Get(3, id, from(0, id)) + weight[id]);
      }
      BA = min(BA, Get(1, id, 0));
      if (Get(1, id, to(0, id)) != INT_MAX && Get(2, id, from(0, id)) != INT_MAX) {
        BA = min(BA, Get(1, id, to(0, id)) + Get(2, id, from(0, id)) + weight[id]); 
      }
      if (AB == INT_MAX || BA == INT_MAX) {
        continue;
      }
      ans = min(ans, AB + BA + cost[id]);
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63