oj.uz

Submission #244939

# Submission time Handle Problem Language Result Execution time Memory
244939 2020-07-05T09:41:12 Z rama_pang Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 123 ms 3056 KB 
#include <bits/stdc++.h>
using namespace std;

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];
int dist[5][MAXN];
int sptree[5][MAXM];

int 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] = 1e9;
  }

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.emplace(0, s);
  auto dt = dist[k];
  auto pr = par[k];
  dt[s] = 0;
  pr[s] = -1;
  while (!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    if (dt[u] != d) {
      continue;
    }
    if (u == target) {
      return d;
    }
    if (pr[u] != -1) {
      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] = -1;
        pq.emplace(dt[v], v);
      } 
    }
  }
  return 1e9;
}

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(N, 2, radj); // 1 to N, reverse
  Dijkstra(1, 3, radj); // N to 1, reverse
  int ans = dist[0][N] + dist[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) {
      int d1 = min(dist[0][N], dist[0][v] + c + dist[2][u]);
      int d2 = min(dist[1][1], dist[1][v] + c + dist[3][u]);
      if (d1 < 1e9 && d2 < 1e9) {
        ans = min(ans, d + d1 + d2);
      }
    } else {
      int d1 = Dijkstra(1, 4, adj, i, v, u, c, N);
      int d2 = Dijkstra(N, 4, adj, i, v, u, c, 1);
      if (d1 < 1e9 && d2 < 1e9) {
        ans = min(ans, d + d1 + d2);
      }
    }
  }
  if (ans > 1.5e9) {
    ans = -1;
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 15 ms 384 KB Output is correct
4 Correct 19 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2844 KB Output is correct
2 Correct 123 ms 2940 KB Output is correct
3 Correct 86 ms 3056 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 9 ms 512 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 60 ms 2792 KB Output is correct
10 Correct 57 ms 2784 KB Output is correct
11 Correct 105 ms 2924 KB Output is correct
12 Correct 98 ms 2936 KB Output is correct
13 Correct 112 ms 2924 KB Output is correct
14 Correct 91 ms 2928 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 512 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 15 ms 384 KB Output is correct
4 Correct 19 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -