oj.uz

Submission #752313

# Submission time Handle Problem Language Result Execution time Memory
752313 2023-06-02T17:51:17 Z tch1cherin Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 360 ms 158156 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;

struct cmp {
  bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
    return a.first > b.first;
  }
};

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;

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;
  priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> 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[e]]) {
        dist[to[e]] = dist[u] + weight[e];
        if (flag) path[to[e]] = e;
        q.emplace(dist[to[e]], to[e]);
      }
    }
  }
}

void _solve(int g, int start, int it) {
  dijkstra(start, g, true);
  memcpy(dist_i[it], dist, sizeof dist);
  for (int i = 0; i < n; i++) {
    if (path[i] != -1) {
      dijkstra(start, g, false, path[i]);
      memcpy(dist_w[it][path[i]], dist, sizeof dist);
    }
  }
}

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[id]) != INT_MAX && Get(3, id, from[id]) != INT_MAX) {
        AB = min(AB, Get(0, id, to[id]) + Get(3, id, from[id]) + weight[id]);
      }
      BA = min(BA, Get(1, id, 0));
      if (Get(1, id, to[id]) != INT_MAX && Get(2, id, from[id]) != INT_MAX) {
        BA = min(BA, Get(1, id, to[id]) + Get(2, id, from[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 156876 KB Output is correct
2 Correct 65 ms 156868 KB Output is correct
3 Correct 73 ms 156900 KB Output is correct
4 Correct 73 ms 156836 KB Output is correct
5 Correct 70 ms 156832 KB Output is correct
6 Correct 64 ms 156860 KB Output is correct
7 Correct 62 ms 156824 KB Output is correct
8 Correct 61 ms 156816 KB Output is correct
9 Correct 61 ms 156904 KB Output is correct
10 Correct 82 ms 156928 KB Output is correct
11 Correct 88 ms 156828 KB Output is correct
12 Incorrect 74 ms 156924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 158064 KB Output is correct
2 Incorrect 308 ms 158156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 156800 KB Output is correct
2 Correct 60 ms 156876 KB Output is correct
3 Correct 119 ms 157728 KB Output is correct
4 Correct 69 ms 156848 KB Output is correct
5 Correct 136 ms 158028 KB Output is correct
6 Correct 58 ms 156804 KB Output is correct
7 Correct 62 ms 156880 KB Output is correct
8 Incorrect 83 ms 157956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 156876 KB Output is correct
2 Correct 65 ms 156868 KB Output is correct
3 Correct 73 ms 156900 KB Output is correct
4 Correct 73 ms 156836 KB Output is correct
5 Correct 70 ms 156832 KB Output is correct
6 Correct 64 ms 156860 KB Output is correct
7 Correct 62 ms 156824 KB Output is correct
8 Correct 61 ms 156816 KB Output is correct
9 Correct 61 ms 156904 KB Output is correct
10 Correct 82 ms 156928 KB Output is correct
11 Correct 88 ms 156828 KB Output is correct
12 Incorrect 74 ms 156924 KB Output isn't correct
13 Halted 0 ms 0 KB -