Submission #1280909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280909		avighna	Closing Time (IOI23_closing)	C++20	0 / 100	147 ms	27580 KiB

closing

#include <bits/stdc++.h>

using int64 = long long;

int max_score(int n, int a, int b, long long k, std::vector<int> u, std::vector<int> v, std::vector<int> w) {
  std::vector<std::vector<std::pair<int, int64>>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[u[i]].push_back({v[i], w[i]});
    adj[v[i]].push_back({u[i], w[i]});
  }

  int64 inf = 1e15;

  auto dijkstra = [&](int u) {
    std::vector<int64> dist(n, inf);
    std::priority_queue<std::pair<int, int>> pq;
    dist[u] = 0;
    pq.push({-dist[u], u});
    std::vector<bool> vis(n);
    vis[u] = true;
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      d = -d;
      for (auto &[i, w] : adj[u]) {
        if (vis[i] or dist[i] <= d + w) {
          continue;
        }
        dist[i] = d + w;
        vis[i] = true;
        pq.push({-dist[i], i});
      }
    }
    return dist;
  };

  auto da = dijkstra(a), db = dijkstra(b);
  int ans = 0;
  std::vector<int64> comb;
  for (auto &i : da) {
    comb.push_back(i);
  }
  for (auto &i : db) {
    comb.push_back(i);
  }
  std::sort(comb.begin(), comb.end());
  int64 have = 0;
  for (auto &i : comb) {
    if (have + i <= k) {
      have += i, ans++;
    }
  }
  return ans;
  //   std::vector<int> na(n), nb(n);
  //   std::iota(na.begin(), na.end(), 0);
  //   std::iota(nb.begin(), nb.end(), 0);
  //   std::sort(na.begin(), na.end(), [&](int i, int j) {
  //     if (da[i] != da[j]) {
  //       return da[i] < da[j];
  //     }
  //     return i < j;
  //   });
  //   std::sort(nb.begin(), nb.end(), [&](int i, int j) {
  //     if (db[i] != db[j]) {
  //       return db[i] < db[j];
  //     }
  //     return i > j;
  //   });

  //   int ans = 0;
  //   for (int i = 0; i < n; ++i) {
  //     for (int j = 0; j < n; ++j) {
  //       std::vector<int64> c(n);
  //       for (int _ = 0; _ < i; ++_) {
  //         c[na[_]] = std::max(c[na[_]], da[na[_]]);
  //       }
  //       for (int _ = 0; _ < j; ++_) {
  //         c[nb[_]] = std::max(c[nb[_]], db[nb[_]]);
  //       }
  //       if (std::accumulate(c.begin(), c.end(), 0LL) <= k) {
  //         ans = std::max(ans, i + j);
  //       }
  //     }
  //   }

  //   return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17