oj.uz

Submission #244920

# Submission time Handle Problem Language Result Execution time Memory
244920 2020-07-05T09:28:56 Z rama_pang Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 2932 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 205;
const int MAXM = 50005;

int N, M;
vector<int> adj[MAXN];
vector<int> radj[MAXN];
vector<array<int, 4>> edge;

int par[5][MAXN];
lint dist[5][MAXN];
int sptree[5][MAXM];

lint Dijkstra(int s, int k, vector<int> a[MAXN], int block = -1, int ru = -1, int rv = -1, int rc = -1, int target = -1) {
  for (int i = 0; i < MAXN; i++) {
    dist[k][i] = 1e18;
  }

  priority_queue<pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> pq;
  pq.emplace(0, s);
  auto dt = dist[k];
  auto pr = par[k];
  dt[s] = 0;
  pr[s] = 0;
  while (!pq.empty()) {
    int u = pq.top().second;
    lint d = pq.top().first;
    pq.pop();
    if (dt[u] != d) {
      continue;
    }
    if (u == target) {
      return d;
    }
    sptree[k][pr[u]] = 1;
    for (auto e : a[u]) if (e != block) {
      int v = edge[e][0] ^ edge[e][1] ^ u;
      if (dt[v] > dt[u] + edge[e][2]) {
        dt[v] = dt[u] + edge[e][2];
        pr[v] = e;
        pq.emplace(dt[v], v);
      }
    }
    if (u == ru) {
      int v = rv;
      if (dt[v] > dt[u] + rc) {
        dt[v] = dt[u] + rc;
        pr[v] = block;
        pq.emplace(dt[v], v);
      } 
    }
  }
  return 1e18;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    edge.push_back({u, v, c, d});
    adj[u].emplace_back(i);
    radj[v].emplace_back(i);
  }

  Dijkstra(1, 0, adj); // 1 to N
  Dijkstra(N, 1, adj); // N to 1
  Dijkstra(1, 2, radj); // 1 to N, reverse
  Dijkstra(N, 3, radj); // N to 1, reverse
  // lint ans = dist[0][N] + dist[1][1];
  lint ans = Dijkstra(1, 4, adj, -1, -1, -1, -1, N) + Dijkstra(N, 4, adj, -1, -1, -1, -1, 1);
  for (int i = 0; i < M; i++) {
    int u, v, c, d;
    u = edge[i][0], v = edge[i][1], c = edge[i][2], d = edge[i][3];
    // if (sptree[0][i] == 0 && sptree[1][i] == 0) {
    //   ans = min(ans, d + min(dist[0][N], dist[0][v] + c + dist[2][u]) + 
    //                      min(dist[1][1], dist[1][v] + c + dist[3][u]));
    // } else {
      ans = min(ans, d + Dijkstra(1, 4, adj, i, v, u, c, N) + Dijkstra(N, 4, adj, i, v, u, c, 1));
    // }
  }
  if (ans > 1e17) {
    ans = -1;
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 36 ms 384 KB Output is correct
4 Correct 45 ms 384 KB Output is correct
5 Correct 18 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 83 ms 512 KB Output is correct
11 Correct 80 ms 512 KB Output is correct
12 Correct 87 ms 632 KB Output is correct
13 Correct 32 ms 508 KB Output is correct
14 Correct 35 ms 632 KB Output is correct
15 Correct 28 ms 512 KB Output is correct
16 Correct 44 ms 512 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Execution timed out 1090 ms 2932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 36 ms 384 KB Output is correct
4 Correct 45 ms 384 KB Output is correct
5 Correct 18 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 83 ms 512 KB Output is correct
11 Correct 80 ms 512 KB Output is correct
12 Correct 87 ms 632 KB Output is correct
13 Correct 32 ms 508 KB Output is correct
14 Correct 35 ms 632 KB Output is correct
15 Correct 28 ms 512 KB Output is correct
16 Correct 44 ms 512 KB Output is correct
17 Execution timed out 1083 ms 2800 KB Time limit exceeded
18 Halted 0 ms 0 KB -