oj.uz

Submission #707258

# Submission time Handle Problem Language Result Execution time Memory
707258 2023-03-08T17:30:30 Z lto5 Relay Marathon (NOI20_relaymarathon) C++14
25 / 100
 1335 ms 118952 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int64_t INF = 0x3f3f3f3f3f3f3f3f;

template <typename T>
bool minimize(T& a, T b) {
  if (a > b) {
    return a = b, 1;
  }
  return 0;
}

int n, m, k;
vector<pair<int, int>> g[N];
int spec[N];

tuple<int64_t, int, int> best_pair() {
  vector<int64_t> d(n + 1, INF);
  vector<int> head(n + 1, 0);
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  for (int i = 1; i <= n; i++) {
    if (spec[i]) {
      head[i] = i;
      d[i] = 0;
      pq.emplace(d[i], i);
    }
  }
  while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (d[u] != du) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        head[v] = head[u];
        pq.emplace(d[v], v);
      }
    }
  }
  int64_t best = INF;
  int best_u = -1, best_v = -1;
  for (int u = 1; u <= n; u++) {
    for (auto [v, w] : g[u]) {
      if (d[u] != INF && d[v] != INF && head[u] != head[v]) {
        if (minimize(best, d[u] + d[v] + w)) {
          best = d[u] + d[v] + w;
          best_u = head[u];
          best_v = head[v];
        }
      }
    }
  }
  return {best, best_u, best_v};
}

pair<int64_t, int> nearest_spec(int s) {
  vector<int64_t> d(n + 1, INF);
  priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
  d[s] = 0;
  pq.emplace(d[s], s);
  while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (d[u] != du) {
      continue;
    }
    if (spec[u]) {
      return {d[u], u};
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.emplace(d[v], v);
      }
    }
  }
  return {INF, 0};
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> m >> k;
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  while (k--) {
    int u;
    cin >> u;
    spec[u] = 1;
  }
  // {a, b, c, d}
  // d(a, b) + d(c, d) min
  // (x, y) = min pair
  /* {x, y} is subset of {a, b, c, d}
   * x != {a, b, c, d} or y != {a, b, c, d} : change something by {x, y} and get better answer
   */

  auto [min_d, x, y] = best_pair();
  int64_t best = INF;
  spec[x] = spec[y] = 0;
  // a = x, b = y
  {
    auto [second_min_d, z, t] = best_pair();
    minimize(best, min_d + second_min_d);
  }
  // a = x, c = y
  {
    auto [nearest_a, z] = nearest_spec(x);
    spec[z] = 0;
    auto [nearest_b, t] = nearest_spec(y);
    minimize(best, nearest_a + nearest_b);
  }
  cout << best;
  return 0;
}

Compilation message

RelayMarathon.cpp: In function 'std::tuple<long int, int, int> best_pair()':
RelayMarathon.cpp:31:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     auto [du, u] = pq.top();
      |          ^
RelayMarathon.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp: In function 'std::pair<long int, int> nearest_spec(int)':
RelayMarathon.cpp:66:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     auto [du, u] = pq.top();
      |          ^
RelayMarathon.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for (auto [v, w] : g[u]) {
      |               ^
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:112:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |   auto [min_d, x, y] = best_pair();
      |        ^
RelayMarathon.cpp:117:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     auto [second_min_d, z, t] = best_pair();
      |          ^
RelayMarathon.cpp:122:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     auto [nearest_a, z] = nearest_spec(x);
      |          ^
RelayMarathon.cpp:124:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     auto [nearest_b, t] = nearest_spec(y);
      |          ^
RelayMarathon.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8008 KB Output is correct
2 Correct 10 ms 4564 KB Output is correct
3 Correct 1226 ms 103844 KB Output is correct
4 Correct 598 ms 51404 KB Output is correct
5 Correct 149 ms 13716 KB Output is correct
6 Correct 145 ms 11492 KB Output is correct
7 Correct 177 ms 14744 KB Output is correct
8 Correct 66 ms 8056 KB Output is correct
9 Correct 104 ms 10764 KB Output is correct
10 Correct 81 ms 8936 KB Output is correct
11 Correct 1310 ms 110912 KB Output is correct
12 Correct 95 ms 9316 KB Output is correct
13 Correct 362 ms 32912 KB Output is correct
14 Correct 170 ms 15264 KB Output is correct
15 Correct 1285 ms 108868 KB Output is correct
16 Correct 44 ms 7424 KB Output is correct
17 Correct 868 ms 79076 KB Output is correct
18 Correct 9 ms 4692 KB Output is correct
19 Correct 1335 ms 118952 KB Output is correct
20 Correct 185 ms 14472 KB Output is correct
21 Correct 154 ms 13136 KB Output is correct
22 Correct 71 ms 8844 KB Output is correct
23 Correct 20 ms 6604 KB Output is correct
24 Correct 824 ms 84028 KB Output is correct
25 Correct 128 ms 10932 KB Output is correct
26 Correct 54 ms 8028 KB Output is correct
27 Correct 84 ms 9920 KB Output is correct
28 Correct 13 ms 5588 KB Output is correct
29 Correct 173 ms 14592 KB Output is correct
30 Correct 302 ms 26296 KB Output is correct

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -