Submission #1186128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186128		raspy	Nile (IOI24_nile)	C++20	32 / 100	58 ms	11960 KiB

nile

#include "nile.h"
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
typedef long long ll;

const ll inf = 1e9+10;
vector<ll> par;
vector<ll> mn;
vector<ll> sz;
vector<ll> sm;

ll mnz(int x)
{
  return par[x] = (x==par[x]?x:mnz(par[x]));
}

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e)
{
  int n = a.size();
  int q = e.size();
  par = vector<ll>(n, 0);
  mn = vector<ll>(n, inf);
  sz = vector<ll>(n, 1);
  vector<ll> ixsw(n);
  iota(ixsw.begin(), ixsw.end(), 0);
  sort(ixsw.begin(), ixsw.end(), [&w](int i, int j)
  {
    return w[i] < w[j];
  });
  iota(par.begin(), par.end(), 0);
  vector<ll> rez(q);
  vector<pair<ll, ll>> qr;
  for (int i = 0; i < q; i++)
    qr.push_back({e[i], i});
  sort(qr.begin(), qr.end());
  vector<pair<ll, ll>> edges;
  for (int i = 0; i+1 < n; i++)
    edges.push_back({ixsw[i], ixsw[i+1]});
  sort(edges.begin(), edges.end(), [&w](pair<ll, ll> i1, pair<ll, ll> i2)
  {
    int r1 = abs(w[i1.first]-w[i1.second]);
    int r2 = abs(w[i2.first]-w[i2.second]);
    return r1 < r2;
  });
  int j = 0;
  int tre = 0;
  for (int i = 0; i < n; i++){
    mn[ixsw[i]] = a[ixsw[i]]-b[ixsw[i]];
    tre += a[ixsw[i]];
  }
  for (int i = 0; i < q; i++)
  {
    auto [ds, ix] = qr[i];
    while (j<edges.size())
    {
      auto [i1, i2] = edges[j];
      int r = abs(w[i1]-w[i2]);
      if (r > ds)
        break;
      int x = mnz(i1);
      int y = mnz(i2);
      if (x==y) continue;
      if (sz[y]%2)
        tre-=mn[y];
      if (sz[x]%2)
        tre-=mn[x];
      par[y] = x;
      sz[x] += sz[y];
      mn[x] = min(mn[x], mn[y]);
      if (sz[x]%2)
        tre+=mn[x];
      j++;
    }
    rez[ix] = tre;
  }
  return rez;
}

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