oj.uz

Submission #1049872

# Submission time Handle Problem Language Result Execution time Memory
1049872 2024-08-09T05:51:13 Z avighna Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 1153 ms 228400 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());
  for (ll i = 0; i < std::min(best1.size(), size_t(5)); ++i) {
    for (ll j = 0; j < std::min(best2.size(), size_t(5)); ++j) {
      if (best1[i].second != best2[j].second) {
        ans = std::min(ans, best1[i].first + best2[j].second);
      }
    }
  }
  std::cout << ans << '\n';
}

Compilation message

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:120:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'const long unsigned int' [-Wsign-compare]
  120 |   for (ll i = 0; i < std::min(best1.size(), size_t(5)); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:121:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'const long unsigned int' [-Wsign-compare]
  121 |     for (ll j = 0; j < std::min(best2.size(), size_t(5)); ++j) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 34 ms 11408 KB Output is correct
2 Correct 6 ms 5892 KB Output is correct
3 Correct 866 ms 225864 KB Output is correct
4 Correct 434 ms 97316 KB Output is correct
5 Correct 116 ms 22456 KB Output is correct
6 Correct 77 ms 17920 KB Output is correct
7 Correct 109 ms 25068 KB Output is correct
8 Correct 38 ms 13000 KB Output is correct
9 Correct 80 ms 16940 KB Output is correct
10 Correct 58 ms 13580 KB Output is correct
11 Correct 947 ms 228400 KB Output is correct
12 Correct 58 ms 14284 KB Output is correct
13 Correct 300 ms 60204 KB Output is correct
14 Correct 141 ms 25232 KB Output is correct
15 Correct 1008 ms 225124 KB Output is correct
16 Correct 42 ms 10760 KB Output is correct
17 Correct 785 ms 150392 KB Output is correct
18 Correct 9 ms 6044 KB Output is correct
19 Correct 1153 ms 228232 KB Output is correct
20 Correct 155 ms 23032 KB Output is correct
21 Correct 135 ms 22804 KB Output is correct
22 Correct 57 ms 13136 KB Output is correct
23 Correct 20 ms 8976 KB Output is correct
24 Correct 617 ms 161900 KB Output is correct
25 Correct 71 ms 17148 KB Output is correct
26 Correct 48 ms 12640 KB Output is correct
27 Correct 55 ms 15764 KB Output is correct
28 Correct 8 ms 7696 KB Output is correct
29 Correct 104 ms 23808 KB Output is correct
30 Correct 196 ms 47684 KB Output is correct

Subtask #4
0 / 58.0

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