Submission #1158008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158008		LucaLucaM	Closing Time (IOI23_closing)	C++20	0 / 100	93 ms	28860 KiB

closing

#include "closing.h"

#include <iostream>
#include <algorithm>
#include <cassert>
#include <vector>

using ll = long long;

const int NMAX = 2e5;
const ll INF = 1e18;

std::vector<std::vector<std::pair<int, int>>> g;

void dfs(int u, int p, std::vector<ll> &d) {
  for (const auto &[v, c] : g[u])  {
    if (v != p) {
      d[v] = d[u] + c;
      dfs(v, u, d);
    }
  }  
}

int max_score(int n, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    g.clear();
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
      g[U[i]].push_back({V[i], W[i]});
      g[V[i]].push_back({U[i], W[i]});
    }

    std::vector<ll> dx(n, 0), dy(n, 0);

    dfs(X, -1, dx);
    dfs(Y, -1, dy);

    std::vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
      a[i] = std::min(dx[i], dy[i]);
      b[i] = std::max(dx[i], dy[i]);
    }

    // for (int i = 0; i < n; i++) {
    //   std::cout << a[i] << ' ' << b[i] << '\n';
    // }
    // std::cout << "\n\n";
    
    // sunt linie si am cel putin unu care apare de doua ori
    
    ll aux = K;

    for (int i = X + 1; i < Y; i++) {
      K -= a[i];
    }

    std::vector<int> upgrades;
    for (int i = 0; i < n; i++) {
      if (X < i && i < Y) {
        upgrades.push_back(b[i] - a[i]);
      } else {
        upgrades.push_back(a[i]);
      }
    }

    std::sort(upgrades.begin(), upgrades.end());

    int caz1 = Y - X - 1;
    if (K < 0) {
      caz1 = -1e9;
    }
    for (const auto &x : upgrades) {
      if (K >= x) {
        caz1++;
        K -= x;
      } else {
        break;
      }
    }

    upgrades.clear();
    for (int i = 0; i < n; i++) {
      upgrades.push_back(a[i]);
    }

    std::sort(upgrades.begin(), upgrades.end());

    int caz2 = 0;

    K = aux;

    for (const auto &x : upgrades) {
      if (K >= x) {
        caz2++;
        K -= x;
      }
    }

    return std::max(caz1, caz2);
  }

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