oj.uz

Submission #752225

# Submission time Handle Problem Language Result Execution time Memory
752225 2023-06-02T14:22:01 Z tch1cherin Olympic Bus (JOI20_ho_t4) C++17
26 / 100
 1000 ms 170908 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

struct edge {
  int from, to, weight, cost, id;

  edge() {}

  edge(int _from, int _to, int _weight, int _cost, int _id) : from(_from), to(_to), weight(_weight), cost(_cost), id(_id) {}
};

struct node {
  int distance, parent;

  node() {
    distance = INT_MAX;
    parent = -1;
  }

  node(int _distance, int _parent) : distance(_distance), parent(_parent) {}
};

struct result {
  int edge;
  vector<int> distances; 
};

vector<node> dijkstra(vector<vector<edge>> graph, int start) {
  int n = (int)graph.size();
  vector<node> answer(n);
  min_heap<pair<int, int>> q;
  q.emplace(0, start);
  answer[start].distance = 0;
  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();
    if (answer[u].distance > d) {
      continue;
    }
    for (auto [from, to, weight, cost, id] : graph[u]) {
      if (answer[from].distance + weight < answer[to].distance) {
        answer[to] = node(answer[from].distance + weight, id);
        q.emplace(answer[to].distance, to);
      }
    }
  }
  return answer;
}

vector<vector<edge>> transpose(vector<vector<edge>> graph) {
  int n = (int)graph.size();
  vector<vector<edge>> new_graph(n);
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      new_graph[to].emplace_back(to, from, weight, cost, id);
    }
  }
  return new_graph;
}

vector<vector<int>> find_shortest_paths_without_each_edge(vector<vector<edge>> graph, int start) {
  int n = (int)graph.size();
  int m = 0;
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      m = max(m, 1 + id);
    }
  }
  vector<node> result = dijkstra(graph, start);
  vector<int> dist(n);
  for (int i = 0; i < n; i++) {
    dist[i] = result[i].distance;
  }
  vector<vector<int>> answer(m, dist);
  for (auto [distance, parent] : result) {
    if (parent != -1) {
      vector<vector<edge>> new_graph = graph;
      for (int u = 0; u < n; u++) {
        for (int i = 0; i < (int)new_graph[u].size(); i++) {
          auto [from, to, weight, cost, id] = new_graph[u][i];
          if (id == parent) {
            new_graph[u].erase(new_graph[u].begin() + i);
            break;
          }  
        }
      }
      vector<node> new_result = dijkstra(new_graph, start);
      for (int i = 0; i < n; i++) {
        answer[parent][i] = new_result[i].distance;  
      }
    }
  }
  return answer;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int from, to, weight, cost;
    cin >> from >> to >> weight >> cost;
    from--, to--;
    graph[from].emplace_back(from, to, weight, cost, i);
  }
  vector<vector<edge>> rev_graph = transpose(graph);
  vector<vector<int>> result_a = find_shortest_paths_without_each_edge(graph, 0);
  vector<vector<int>> result_b = find_shortest_paths_without_each_edge(graph, n - 1);
  vector<vector<int>> rev_result_a = find_shortest_paths_without_each_edge(rev_graph, 0);
  vector<vector<int>> rev_result_b = find_shortest_paths_without_each_edge(rev_graph, n - 1);
  int ans = INT_MAX;
  int ab = dijkstra(graph, 0)[n - 1].distance;
  int ba = dijkstra(graph, n - 1)[0].distance;
  if (ab != INT_MAX && ba != INT_MAX) {
    ans = min(ans, ab + ba);
  }
  for (int u = 0; u < n; u++) {
    for (auto [from, to, weight, cost, id] : graph[u]) {
      int AB = INT_MAX, BA = INT_MAX;
      AB = min(AB, result_a[id][n - 1]);
      if (result_a[id][to] != INT_MAX && rev_result_b[id][from] != INT_MAX) {
        AB = min(AB, result_a[id][to] + rev_result_b[id][from] + weight);
      }
      BA = min(BA, result_b[id][0]);
      if (result_b[id][to] != INT_MAX && rev_result_a[id][from] != INT_MAX) {
        BA = min(BA, result_b[id][to] + rev_result_a[id][from] + weight); 
      }
      if (AB == INT_MAX || BA == INT_MAX) {
        continue;
      }
      ans = min(ans, AB + BA + cost);
    }
  }
  cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3704 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 42 ms 3700 KB Output is correct
4 Correct 45 ms 3712 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 53 ms 3756 KB Output is correct
11 Correct 54 ms 3700 KB Output is correct
12 Correct 50 ms 3780 KB Output is correct
13 Correct 17 ms 3760 KB Output is correct
14 Correct 30 ms 3712 KB Output is correct
15 Correct 31 ms 3716 KB Output is correct
16 Correct 29 ms 3740 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 170652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3652 KB Output is correct
2 Correct 8 ms 1108 KB Output is correct
3 Correct 557 ms 132940 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 788 ms 170556 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 377 ms 170892 KB Output is correct
9 Correct 375 ms 170812 KB Output is correct
10 Correct 563 ms 170536 KB Output is correct
11 Correct 560 ms 170648 KB Output is correct
12 Correct 596 ms 170764 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 627 ms 170908 KB Output is correct
20 Correct 579 ms 170580 KB Output is correct
21 Correct 548 ms 170620 KB Output is correct
22 Correct 616 ms 170552 KB Output is correct

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3704 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 42 ms 3700 KB Output is correct
4 Correct 45 ms 3712 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 53 ms 3756 KB Output is correct
11 Correct 54 ms 3700 KB Output is correct
12 Correct 50 ms 3780 KB Output is correct
13 Correct 17 ms 3760 KB Output is correct
14 Correct 30 ms 3712 KB Output is correct
15 Correct 31 ms 3716 KB Output is correct
16 Correct 29 ms 3740 KB Output is correct
17 Execution timed out 1066 ms 170652 KB Time limit exceeded
18 Halted 0 ms 0 KB -