Submission #840625

#	Time	Username	Problem	Language	Result	Execution time	Memory
840625		bicsi	Closing Time (IOI23_closing)	C++17	35 / 100	1042 ms	33188 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]);
  }
  auto precomp = [&](int src) {
    vector<int> q = {src};
    vector<long long> ret(N, -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);
        }
      }
    }
    return ret;
  };

  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  
  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 = [&](int root) {
    long long rem = K;
    vector<tuple<long long, int, int>> v;
    vector<vector<bool>> taken(2, vector<bool>(N, false));
    int ans = 0;
    for (int i = 0; i < N; ++i) {
      long long a = dist[0][i], b = dist[1][i];
      if (i == root) {
        taken[0][i] = taken[1][i] = true;
        rem -= max(a, b);
        ans += 2;
      } else if (a + b == dist[0][Y]) {
        if (a < b) {
          // v.emplace_back(2 * a, i, 0);
          rem -= a; taken[0][i] = true;
          v.emplace_back(2 * (b - a), i, 1);
          ans += 1;
        } else {
          rem -= b; taken[1][i] = true;
          v.emplace_back(2 * (a - b), i, 0);
          // v.emplace_back(2 * b, i, 1);
          ans += 1;
        }
      } else {
        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(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, i, 2);
        }
      }
    }

    if (rem < 0) return 0;

    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);
      // cerr << "take: " << i << " " << z << endl;
      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;
  };

  int ans = try_indep();
  for (int root = 0; root < N; ++root) {
    if (dist[0][root] + dist[1][root] != dist[0][Y]) continue;
    ans = max(ans, try_dep(root));
  }
  return ans;
}

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