oj.uz

Submission #679662

# Submission time Handle Problem Language Result Execution time Memory
679662 2023-01-08T20:27:59 Z peijar Cities (BOI16_cities) C++17
74 / 100
 6000 ms 239300 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXK = 5;
const int MAXN = 1e5;
const int INF = 1e18;
int dp[MAXN][1 << MAXK];
vector<pair<int, int>> adj[MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbImportants, nbAretes;
  cin >> nbSommet >> nbImportants >> nbAretes;
  vector<int> importants(nbImportants);
  for (int &x : importants) {
    cin >> x;
    --x;
  }
  for (int i = 0; i < nbAretes; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    adj[u].emplace_back(v, c);
    adj[v].emplace_back(u, c);
  }

  auto compare = [&](tuple<int, int, int> l, tuple<int, int, int> r) {
    return get<2>(l) > get<2>(r);
  };

  priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                 decltype(compare)>
      pq(compare);
  for (int i = 0; i < nbSommet; ++i)
    for (int msk = 0; msk < (1 << nbImportants); ++msk)
      dp[i][msk] = INF;

  for (int i = 0; i < nbImportants; ++i) {
    dp[importants[i]][1 << i] = 0;
    pq.emplace(importants[i], 1 << i, 0);
  }

  while (!pq.empty()) {
    auto [u, msk, cost] = pq.top();
    pq.pop();
    if (dp[u][msk] < cost)
      continue;
    for (int msk2 = 0; msk2 < (1 << nbImportants); ++msk2)
      if (dp[u][msk | msk2] > dp[u][msk] + dp[u][msk2]) {
        dp[u][msk | msk2] = dp[u][msk] + dp[u][msk2];
        pq.emplace(u, msk | msk2, dp[u][msk | msk2]);
      }
    for (auto [v, w] : adj[u])
      if (dp[v][msk] > dp[u][msk] + w) {
        dp[v][msk] = dp[u][msk] + w;
        pq.emplace(v, msk, dp[u][msk]);
      }
  }
  int sol = INF;
  for (int u = 0; u < nbSommet; ++u)
    sol = min(sol, dp[u][(1 << nbImportants) - 1]);
  cout << sol << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2580 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 67152 KB Output is correct
2 Correct 797 ms 54184 KB Output is correct
3 Correct 345 ms 41264 KB Output is correct
4 Correct 73 ms 16836 KB Output is correct
5 Correct 351 ms 48520 KB Output is correct
6 Correct 61 ms 16084 KB Output is correct
7 Correct 4 ms 3348 KB Output is correct
8 Correct 3 ms 3120 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3920 KB Output is correct
2 Correct 9 ms 3924 KB Output is correct
3 Correct 5 ms 3268 KB Output is correct
4 Correct 7 ms 3476 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2855 ms 141020 KB Output is correct
2 Correct 2579 ms 140192 KB Output is correct
3 Correct 1355 ms 59872 KB Output is correct
4 Correct 1667 ms 79236 KB Output is correct
5 Correct 340 ms 30296 KB Output is correct
6 Correct 88 ms 18976 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6021 ms 239300 KB Time limit exceeded
2 Halted 0 ms 0 KB -