Submission #839877

#	Time	Username	Problem	Language	Result	Execution time	Memory
839877		bicsi	Closing Time (IOI23_closing)	C++17	17 / 100	91 ms	24920 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<int> xy = {X, Y};
  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  vector<vector<int>> taken = {vector<int>(N, 0), vector<int>(N, 0)};
  vector<vector<int>> seen = {vector<int>(N, 0), vector<int>(N, 0)};
  priority_queue<tuple<long long, int, int>> pq;
  auto push = [&](int z, int node) {
    if (seen[z][node]) return;
    seen[z][node] = true;
    pq.emplace(-2 * dist[z][node], z, node);
    if (seen[!z][node] && max(dist[0][node], dist[1][node]) < 
        2 * min(dist[0][node], dist[1][node])) {
      pq.emplace(-(dist[z][node] + dist[!z][node]), 3, node);
    }
  };

  push(0, xy[0]); push(1, xy[1]);
  vector<pair<int, int>> nxt;

  auto take = [&](int z, int node) {
    if (taken[z][node]) return true;
    long long d = dist[z][node];
    if (taken[!z][node]) d = max(0LL, d - dist[!z][node]);
    //cerr << "try take: " << node << " d=" << d << endl;
    if (d > K) return false;
    K -= d;
    taken[z][node] = true;
    for (auto [vec, _] : graph[node])
      nxt.emplace_back(z, vec);
    //cerr << "ok" << endl;
    return true;
  };

  while (pq.size()) {
    auto [_, z, node] = pq.top(); pq.pop();
    if (z == 3) {
      long long oldK = K;
      int oldTake[2] = {taken[0][node], taken[1][node]};
      if (!take(0, node) || !take(1, node)) {
        K = oldK;
        taken[0][node] = oldTake[0];
        taken[1][node] = oldTake[1];
        nxt.clear();
      }
    } else {
      take(z, node);
    }
    for (auto [z, vec] : nxt)
      push(z, vec);
    nxt.clear();
  }
  /*
  for (int z = 0; z < 2; ++z) {
    for (int i = 0; i < N; ++i)
      cerr << taken[z][i];
    cerr << endl;
  }
  */
  int ans = 0;
  for (int z = 0; z < 2; ++z) 
    for (int i = 0; i < N; ++i)
      ans += taken[z][i];
  return ans;
}

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