Submission #1196575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196575		abczz	Closing Time (IOI23_closing)	C++20	100 / 100	262 ms	64156 KiB

closing

#include "closing.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long

using namespace std;

vector <ll> V, U;
vector <array<ll, 3>> T;
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
bool B[200000];
bool done[200000];
ll dist[200000], P[200000];
vector <array<ll, 2>> adj[200000];
ll n, x, y, k, l, tot, tot2, f, mn, mnid;
bool dfs(ll u, ll p, ll w) {
  if (u == y) {
    U.push_back(w);
    V.push_back(u);
    B[u] = 1;
    l = tot = w;
    return 1;
  }
  for (auto [v, z] : adj[u]) {
    if (v == p) continue;
    auto ok = dfs(v, u, w+z);
    if (ok) {
      U.push_back(w);
      V.push_back(u);
      B[u] = 1;
      tot += max(w, l-w);
      tot2 += min(w, l-w);
      return 1;
    }
  }
  return 0;
}
void dfs2(ll u, ll p, ll w) {
  for (auto [v, z] : adj[u]) {
    if (v == p) continue;
    P[v] = u;
    dfs2(v, u, w+z);
  }
}
void solve(ll u, ll p, ll w1, ll w2) {
  if (!B[u]) {
    T.push_back({2*w1, 2, u});
    pq.push({2*w1, 2, u});
    if (w1 <= w2-w1) {
      pq.push({2*(w2-w1), 2, u});
      T.push_back({2*(w2-w1), 2, u});
    }
    else {
      pq.push({w2, 1, u});
      T.push_back({w2, 1, u});
    }
  }
  else if (abs(w1-(l-w1)) < mn) mn = abs(w1-(l-w1)), mnid = u;
  for (auto [v, z] : adj[u]) {
    if (v == p) continue;
    if (B[u] && !B[v]) solve(v, u, min(w1, l-w1)+z, max(w1, l-w1)+z);
    else solve(v, u, w1+z, w2+z);
  }
}
void case1() {
  while (!pq.empty()) pq.pop();
  dfs(x, -1, 0);
  solve(x, -1, 0, 0);
  ll s = k, res = 0;
  if (s >= tot) {
    res = 2*(ll)V.size();
    s -= tot;
    vector <array<ll, 2> > tmp;
    while (!pq.empty()) {
      auto [w, t, u] = pq.top();
      pq.pop();
      //cout << s << " " << w << " " << t << " " << u << endl;
      if (t == 2 && s >= w/2 && !done[u]) {
        tmp.push_back({w/2, u});
        s -= w/2, ++res;
      }
      else if (t == 1 && s >= w) {
        s -= w, res += 2;
        done[u] = 1;
      }
      else if (t == 1) {
        for (int i=(ll)tmp.size()-1; i>=max(0LL, (ll)tmp.size()-3); --i) {
          if (s+tmp[i][0] >= w && P[u] != tmp[i][1]) {
            f = max(f, res+1);
          }
        }
      }
    }
  }
  f = max(f, res);
}
void case2() {
  while (!pq.empty()) pq.pop();
  ll s = k, res = 0;
  pq.push({0, x, 0});
  pq.push({0, y, 0});
  dist[x] = dist[y] = 0;
  while (!pq.empty()) {
    auto [w, u, d] = pq.top();
    pq.pop();
    if (dist[u] != w) continue;
    if (s >= w) s -= w, ++res;
    for (auto [v, z] : adj[u]) {
      if (dist[v] > dist[u]+z) {
        dist[v] = dist[u]+z;
        pq.push({dist[v], v, 0});
      }
    }
  }
  f = max(f, res);
}
void case3() {
  P[mnid] = mnid;
  dfs2(mnid, -1, 0);
  while (!pq.empty()) pq.pop();
  for (int i=0; i<n; ++i) done[i] = 0;
  ll s = k, res = 0;
  if (s >= tot2+mn) {
    s -= tot2+mn;
    res = (ll)V.size() + 1;
    for (int i=0; i<V.size(); ++i) {
      if (V[i] == mnid) continue;
      pq.push({2*(max(U[i], l-U[i])-min(U[i], l-U[i])), 2, V[i]});
    }
    for (auto [x, y, z] : T) {
      pq.push({x, y, z});
    }
    vector <array<ll, 2> > tmp;
    while (!pq.empty()) {
      auto [w, t, u] = pq.top();
      pq.pop();
      //cout << s << " " << w << " " << t << " " << u << endl;
      if (t == 2 && s >= w/2 && !done[u]) {
        tmp.push_back({w/2, u});
        s -= w/2, ++res;
      }
      else if (t == 1 && s >= w) {
        s -= w, res += 2;
        done[u] = 1;
      }
      else if (t == 1) {
        for (int i=(ll)tmp.size()-1; i>=max(0LL, (ll)tmp.size()-3); --i) {
          if (s+tmp[i][0] >= w && P[u] != tmp[i][1]) {
            f = max(f, res+1);
          }
        }
      }
    }
  }
  f = max(f, res);
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> eu, std::vector<int> ev, std::vector<int> W)
{
  for (int i=0; i<N; ++i) {
    adj[i].clear();
    dist[i] = 1e18;
    B[i] = done[i] = 0;
  }
  T.clear();
  V.clear();
  U.clear();
  while (!pq.empty()) pq.pop();
  n = N, x = X, y = Y, k = K, f = -1e18, mn = 1e18, mnid = -1, tot2 = 0;
  for (int i=0; i<N-1; ++i) {
    adj[eu[i]].push_back({ev[i], W[i]});
    adj[ev[i]].push_back({eu[i], W[i]});
  }
  case1();
  case2();
  case3();
  return int(f);
}

• 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