oj.uz

Submission #244945

# Submission time Handle Problem Language Result Execution time Memory
244945 2020-07-05T09:50:16 Z rama_pang Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 31 ms 2548 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] = 2e9;
  }

  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 2e9;
}

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 = (int) min((long long) 2e9, 1ll * dist[0][N] + 1ll * 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((long long) dist[0][N], (long long) dist[0][v] + c + dist[2][u]);
      int d2 = min((long long) dist[1][1], (long long) dist[1][v] + c + dist[3][u]);
      if (d1 < 2e9 && d2 < 2e9) {
        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 < 2e9 && d2 < 2e9) {
      //   ans = min(ans, d + d1 + d2);
      // }
    }
  }
  if (ans >= 2e9) {
    ans = -1;
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2548 KB Output is correct
2 Correct 27 ms 2548 KB Output is correct
3 Correct 28 ms 2544 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 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 Incorrect 5 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 21 ms 2076 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 26 ms 2548 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 25 ms 2396 KB Output is correct
9 Correct 26 ms 2388 KB Output is correct
10 Correct 26 ms 2420 KB Output is correct
11 Correct 27 ms 2412 KB Output is correct
12 Correct 27 ms 2548 KB Output is correct
13 Incorrect 5 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

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