Submission #840588

#	Time	Username	Problem	Language	Result	Execution time	Memory
840588		bicsi	Closing Time (IOI23_closing)	C++17	8 / 100	206 ms	27984 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>

using namespace std;

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
  vector<vector<pair<int, int>>> graph(N);
  for (int i = 0; i < (int)U.size(); ++i) {
    graph[U[i]].emplace_back(V[i], W[i]);
    graph[V[i]].emplace_back(U[i], W[i]);
  }
  vector<int> parent(N, -1);
  auto precomp = [&](int src) {
    vector<int> q = {src};
    vector<long long> ret(N, -1);
    parent[src] = -1;
    ret[src] = 0;
    for (int i = 0; i < N; ++i) {
      int node = q[i];
      for (auto [vec, cost] : graph[node]) {
        if (ret[vec] == -1) {
          ret[vec] = ret[node] + cost;
          q.push_back(vec);
          parent[vec] = node;
        }
      }
    }
    return ret;
  };

  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  
  vector<int> path;
  for (int node = X; node != -1; node = parent[node]) 
    path.push_back(node);
  
  auto try_indep = [&]() {
    vector<long long> v;
    for (int z = 0; z < 2; ++z)
    for (int i = 0; i < N; ++i)
      v.push_back(dist[z][i]);
    sort(v.begin(), v.end());
    long long rem = K;
    int ans = 0;
    for (auto x : v) {
      if (x <= rem) rem -= x, ans += 1;
    }
    return ans;
  };

  auto try_dep = [&]() {
    long long rem = K;
    vector<tuple<long long, int, int>> v;
    vector<bool> inpath(N, false);
    vector<vector<bool>> taken(2, vector<bool>(N, false));
    int ans = 0;
    for (auto x : path) {
      if (dist[0][x] < dist[1][x]) {
        rem -= dist[0][x];
        taken[0][x] = true;
        v.emplace_back(2 * (dist[1][x] - dist[0][x]), x, 1);
        ans += 1;
      } else {
        rem -= dist[1][x];
        taken[1][x] = true;
        v.emplace_back(2 * (dist[0][x] - dist[1][x]), x, 0);
        ans += 1;
      }
      inpath[x] = true;
    }
    if (rem < 0) return 0;
    for (int i = 0; i < N; ++i) {
      if (inpath[i]) continue;
      long long a = dist[0][i], b = dist[1][i];
      if (a < b) {
        if (2 * a <= b) v.emplace_back(2 * a, i, 0), v.emplace_back(2 * (b - a), i, 1);
        else v.emplace_back(a + b, i, 2);
      } else {
        if (2 * b <= a) v.emplace_back(2 * b, i, 1), v.emplace_back(2 * (a - b), i, 0);
        else v.emplace_back(a + b, i, 2);
      }
    }
    sort(v.begin(), v.end());
    for (auto [c, i, z] : v) {
      if (z != 2) c /= 2;
      if (c > rem) break;
      rem -= c;
      ans += (z == 2 ? 2 : 1);
      if (z == 2) {
        assert(taken[0][i] == 0 && taken[1][i] == 0);
        taken[0][i] = 1;
        taken[1][i] = 1;
      } else {
        assert(taken[z][i] == 0);
        taken[z][i] = 1;
      }
    }

    for (int z = 0; z < 2; ++z) {
      for (int i = 0; i < N; ++i) {
        if (taken[z][i] == 0 && dist[z][i] <= rem) {
          return ans + 1;
        }
      }
    }
    return ans;
  };

  long long indep = try_indep();
  long long dep = try_dep();
  cerr << indep << " " << dep << endl;
  return max(indep, dep);
}

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