oj.uz

Submission #1049850

# Submission time Handle Problem Language Result Execution time Memory
1049850 2024-08-09T05:46:13 Z avighna Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 972 ms 228804 KB 
#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

struct Edge {
  ll u, v, w;
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m, k;
  std::cin >> n >> m >> k;
  std::vector<std::vector<std::pair<ll, ll>>> adj(n + 1);
  std::vector<Edge> edges;
  for (ll i = 0, u, v, w; i < m; ++i) {
    std::cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    edges.push_back({u, v, w});
  }
  std::vector<ll> A(k);
  std::vector<bool> special(n + 1);
  for (auto &i : A) {
    std::cin >> i;
    special[i] = true;
  }

  auto get_best = [&]() {
    std::priority_queue<std::pair<ll, std::pair<ll, ll>>> pq;
    std::vector<ll> d(n + 1, inf);
    for (auto &i : A) {
      pq.push({0, {i, i}});
      d[i] = 0;
    }
    std::vector<std::pair<ll, ll>> closest_special(n + 1);
    std::vector<bool> vis(n + 1);
    while (!pq.empty()) {
      ll node = pq.top().second.first, source = pq.top().second.second,
         dist = -pq.top().first;
      pq.pop();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      closest_special[node] = {source, dist};
      for (auto &[i, i_d] : adj[node]) {
        if (dist + i_d < d[i]) {
          d[i] = dist + i_d;
          pq.push({-d[i], {i, source}});
        }
      }
    }

    std::pair<ll, std::pair<ll, ll>> ans = {inf, {0, 0}};
    for (auto &[u, v, w] : edges) {
      if (special[u] and special[v]) {
        ans = std::min(ans, {w, {u, v}});
      }
    }
    for (auto &[u, v, w] : edges) {
      if (closest_special[u].first != closest_special[v].first) {
        ans = std::min(
            ans, {closest_special[u].second + w + closest_special[v].second,
                  {closest_special[u].first, closest_special[v].first}});
      }
    }
    return ans;
  };

  auto sssp = [&](ll x) {
    std::priority_queue<std::pair<ll, ll>> pq;
    pq.push({0, x});
    std::vector<ll> ans(n + 1, inf);
    std::vector<bool> vis(n + 1);
    ans[x] = 0;
    while (!pq.empty()) {
      ll node = pq.top().second, d = -pq.top().first;
      pq.pop();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      for (auto &[i, dist] : adj[node]) {
        if (d + dist < ans[i]) {
          ans[i] = d + dist;
          pq.push({-ans[i], i});
        }
      }
    }
    return ans;
  };

  auto best = get_best();
  auto &[u, v] = best.second;
  special[u] = special[v] = false;
  A.erase(std::remove(A.begin(), A.end(), u), A.end());
  A.erase(std::remove(A.begin(), A.end(), v), A.end());
  auto second_best = get_best();
  ll ans = best.first + second_best.first;
  auto sssp1 = sssp(u);
  std::vector<std::pair<ll, ll>> best1;
  for (ll x = 1; x <= n; ++x) {
    if (x != v and special[x]) {
      best1.push_back({sssp1[x], x});
    }
  }
  auto sssp2 = sssp(v);
  std::vector<std::pair<ll, ll>> best2;
  for (ll y = 1; y <= n; ++y) {
    if (y != u and special[y]) {
      best2.push_back({sssp1[y], y});
    }
  }
  std::sort(best1.begin(), best1.end());
  std::sort(best2.begin(), best2.end());
  if (!best1.empty() and !best2.empty()) {
    if (best1[0].second != best2[0].second) {
      ans = std::min(ans, best1[0].first + best2[0].second);
    } else {
      if (best2.size() >= 2) {
        ans = std::min(ans, best1[0].first + best2[1].second);
      }
      if (best1.size() >= 2) {
        ans = std::min(ans, best1[1].first + best2[0].second);
      }
    }
  }
  std::cout << ans << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 38 ms 12540 KB Output is correct
2 Correct 5 ms 5980 KB Output is correct
3 Correct 850 ms 226644 KB Output is correct
4 Correct 407 ms 96664 KB Output is correct
5 Correct 96 ms 23148 KB Output is correct
6 Correct 83 ms 18952 KB Output is correct
7 Correct 112 ms 25308 KB Output is correct
8 Correct 36 ms 11780 KB Output is correct
9 Correct 67 ms 16900 KB Output is correct
10 Correct 47 ms 13568 KB Output is correct
11 Correct 815 ms 227480 KB Output is correct
12 Correct 62 ms 14796 KB Output is correct
13 Correct 240 ms 60104 KB Output is correct
14 Correct 120 ms 25144 KB Output is correct
15 Correct 830 ms 224160 KB Output is correct
16 Correct 35 ms 10700 KB Output is correct
17 Correct 593 ms 150864 KB Output is correct
18 Correct 4 ms 6036 KB Output is correct
19 Correct 972 ms 228804 KB Output is correct
20 Correct 109 ms 23548 KB Output is correct
21 Correct 98 ms 21984 KB Output is correct
22 Correct 46 ms 13724 KB Output is correct
23 Correct 16 ms 8976 KB Output is correct
24 Correct 549 ms 162404 KB Output is correct
25 Correct 66 ms 17156 KB Output is correct
26 Correct 35 ms 11788 KB Output is correct
27 Correct 64 ms 15148 KB Output is correct
28 Correct 10 ms 7444 KB Output is correct
29 Correct 94 ms 25344 KB Output is correct
30 Correct 217 ms 48680 KB Output is correct

Subtask #4
0 / 58.0

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