Submission #1280912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280912		avighna	Closing Time (IOI23_closing)	C++20	9 / 100	1096 ms	26476 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 = 1e18 + 1;

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

  if (a > b) {
    std::swap(a, b);
  }

  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) {
    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: 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