Submission #841679

#	Time	Username	Problem	Language	Result	Execution time	Memory
841679		garyye	Closing Time (IOI23_closing)	C++17	8 / 100	121 ms	36636 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<int, int> i2;
typedef tuple<ll, int, int, int> i4;

struct Cmp {
  bool operator()(const i4& a, const i4& b) const {
    return get<0>(a) > get<0>(b);
  }
};

typedef priority_queue<i4, vector<i4>, Cmp> heap4;

int max_score(int N, int X, int Y, ll K, 
    vector<int> U, vector<int> V, vector<int> W) {
  vector<vector<i2>> E(N);

  for(int i = 0; i < N - 1; ++i) {
    E[U[i]].push_back({V[i], W[i]});
    E[V[i]].push_back({U[i], W[i]});
  }

  auto calc_dist = [&](int s) {
    vector<ll> D(N, 0);
    function<void(int, int)> rec;
    rec = [&](int u, int p) {
      for(const auto& [v, w] : E[u]) {
        if(v != p) {
          D[v] = D[u] + w;
          rec(v, u);
        }
      }
    };
    rec(s, -1);
    return D;
  };

  auto find_path = [&]() {
    vector<int> path;
    function<bool(int, int)> rec;
    rec = [&](int u, int p) {
      path.push_back(u);
      if(u == Y) {
        return true;
      }
      for(const auto& [v, _] : E[u]) {
        if(v != p && rec(v, u)) {
          return true;
        }
      }
      path.pop_back();
      return false;
    };
    rec(X, -1);
    return path;
  };


  vector<vector<ll>> D = {calc_dist(X), calc_dist(Y)};

  auto solve = [&](heap4& pq, ll k, bool cross) {
    int s = 0;
    while(!pq.empty()) {
      auto [d, u, p, c] = pq.top(); pq.pop();
      if(d > k) {
        break;
      }
      s++;
      k -= d;
      for(auto [v, w]: E[u]) {
        if(v != p) {
          ll b = -1;
          // w > 0, so can't be equal
          if(D[c][v] < D[1-c][v]) {
            b = D[c][v];
          } else if(cross) {
            b = D[c][v] - D[1-c][v];
          }
          if(b != -1) {
            pq.emplace(b, v, u, c);
          }

        }
      }
    }
    return s;
  };


  int ans;
  {
    heap4 pq;
    pq.emplace(0, X, -1, 0);
    pq.emplace(0, Y, -1, 1);
    ans = solve(pq, K, false);
  }


  {
    ll k = K;
    vector<int> P = find_path();

    for(int j = 0; j < P.size(); ++j) {
      k -= min(D[0][P[j]], D[1][P[j]]);
    }

    int i;
    for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
    i--;

    heap4 pq;
    for(auto [v, w]: E[X]) if(v != P[1])          pq.emplace(w, v, X, 0);
    for(auto [v, w]: E[Y]) if(v != P[P.size()-2]) pq.emplace(w, v, Y, 1);

    pq.emplace(D[0][P[i+1]] - D[1][P[i+1]], P[i+1], P[i], 0);
    pq.emplace(D[1][P[i]] - D[0][P[i]], P[i], P[i+1], 1);

    if(k >= 0) {
      ans = max(ans, (int) P.size() + solve(pq, k, true));
    }
  }

  return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int j = 0; j < P.size(); ++j) {
      |                    ~~^~~~~~~~~~
closing.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(i = 0; i < P.size() && D[0][P[i]] < D[1][P[i]]; ++i) {}
      |                ~~^~~~~~~~~~

• 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