Submission #1203436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203436		abczz	Nile (IOI24_nile)	C++20	38 / 100	64 ms	15924 KiB

nile

#include "nile.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

ll P[100000], tot[100000], sz[100000], opt[100000];
ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  vector <array<ll, 3> > X, Q;
  vector <ll> F;
  F.resize(E.size());
  ll n = W.size(), f = 0;
  for (int i=0; i<n; ++i) {
    f += A[i];
    X.push_back({W[i], A[i], B[i]});
  }
  sort(X.begin(), X.end());
  for (int i=0; i<n; ++i) P[i] = i, tot[i] = X[i][2], sz[i] = 1, opt[i] = X[i][1]-X[i][2];
  for (int i=0; i<n-1; ++i) {
    Q.push_back({X[i+1][0]-X[i][0], 0, i});
  }
  for (int i=0; i<E.size(); ++i) {
    Q.push_back({E[i], 1, i});
  }
  sort(Q.begin(), Q.end());
  for (auto [w, ty, u] : Q) {
    if (ty == 0) {
      ll a = dsu(u), b = dsu(u+1);
      f -= tot[a] + (sz[a] & 1 ? opt[a] : 0);
      f -= tot[b] + (sz[b] & 1 ? opt[b] : 0);
      P[a] = b;
      sz[b] += sz[a];
      tot[b] += tot[a];
      opt[b] = min(opt[b], opt[a]);
      f += tot[b] + (sz[b] & 1 ? opt[b] : 0);
    }
    else F[u] = f;
  }
  return F;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18