Submission #1280904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280904		avighna	Closing Time (IOI23_closing)	C++20	9 / 100	1094 ms	26444 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);
  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) {
    return da[i] < da[j];
  });
  std::sort(nb.begin(), nb.end(), [&](int i, int j) {
    return db[i] < db[j];
  });

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

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 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