Submission #1177131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177131		rxlfd314	Closing Time (IOI23_closing)	C++17	100 / 100	192 ms	41128 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

int max_score(int N, int X, int Y, ll K, vt<int> U, vt<int> V, vt<int> W) {
  vt<vt<ari2>> adj(N);
  FOR(i, 0, N-2) {
    adj[U[i]].push_back({V[i], W[i]});
    adj[V[i]].push_back({U[i], W[i]});
  }
  
  auto get_dists = [&](auto &&self, vt<ll> &dist, const int i, const int p) -> void {
    for (const auto &[j, v] : adj[i])
      if (j != p) {
        dist[j] = dist[i] + v;
        self(self, dist, j, i);
      }
  };
  vt<ll> dist_x(N), dist_y(N);
  get_dists(get_dists, dist_x, X, -1);
  get_dists(get_dists, dist_y, Y, -1);
  
  vt<ll> cost1(N), cost2(N), only1;
  FOR(i, 0, N-1) {
    cost1[i] = min(dist_x[i], dist_y[i]);
    cost2[i] = max(dist_x[i], dist_y[i]) - cost1[i];
    only1.push_back(cost1[i]);
  }
  
  int ans1 = 0; {
    sort(all(only1));
    ll lim = K;
    for (const auto &i : only1)
      ans1 += ((lim -= i) >= 0);
  }
  int ans2 = 0; {
    vt<ll> freely = {0};
    vt<pair<ll, int>> both;
    multiset<ll> one;
    ll lim = K;
    FOR(i, 0, N-1) {
      if (dist_x[i] + dist_y[i] == dist_x[Y]) {
        lim -= cost1[i];
        ans2++;
        freely.push_back(cost2[i]);
      } else if (cost2[i] < cost1[i]) {
        both.push_back({cost1[i] + cost2[i], i});
        one.insert(cost1[i]);
      } else {
        freely.push_back(cost1[i]);
        freely.push_back(cost2[i]);
      }
    }
    if (lim < 0)
      ans2 = INT_MIN;
    sort(all(both));
    sort(all(freely));
    
    vt<ll> best_lt(2*N+1, 1e18);
    best_lt[0] = 0;
    ll max_cost2 = 0;
    FOR(ii, 0, size(both) - 1) {
      const auto [v, i] = both[ii];
      best_lt[2*ii+1] = best_lt[2*ii] + min(v - max_cost2, *one.begin());
      best_lt[2*ii+2] = best_lt[2*ii] + v;
      max_cost2 = max(max_cost2, cost2[i]);
      one.erase(one.find(cost1[i]));
    }
    FOR(i, 1, size(freely) - 1)
      freely[i] += freely[i-1];
    #ifdef DEBUG
    FOR(i, 0, size(freely) - 1)
      cout << "freely " << i << ": " << freely[i] << '\n';
    FOR(i, 0, 2*N)
      cout << "best_lt " << i << ": " << best_lt[i] << '\n';
    #endif
    
    int best = 0;
    for (int i = 0, j = size(freely) - 1; i <= 2 * N; i++) {
      for (; j >= 0 && freely[j] + best_lt[i] > lim; j--);
      if (j >= 0)
        best = max(best, i + j);
    }
    ans2 += best;
  }
  
  return max(ans1, ans2);
}

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