Submission #1166769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166769		garyye	Nile (IOI24_nile)	C++20	0 / 100	70 ms	21692 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) do { std::cerr << x; } while (0)

struct DSU {
  vector<int> f;
  DSU(int n) {
    f = vector<int>(n, 0);
    for(int i = 0; i < n; i++) {
      f[i] = i;
    }
  }

  // Only path copmression already log n
  int find(int i) {
    if(f[i] == i) {
      return i;
    }
    return f[i] = find(f[i]);
  }
};

template<class T>
bool cmin(T& a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

const int INF = 1e9 + 10;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int Q = (int)E.size();
  int n = W.size();

  int sumA = 0;

  vector<pair<int, int>> data;

  unordered_map<int, vector<int>> D;
  for(int i = 0; i < n; i++) {
    sumA += A[i];
    D[W[i]].push_back(A[i] - B[i]);
    printf("W[i] = %d D[i] = %d\n", W[i], A[i]-B[i]);
  }
  sort(begin(W), end(W));
  W.resize(unique(begin(W), end(W)) - begin(W));

  for(int i = 0; i < W.size(); i++) {
    printf("%d ", W[i]);
  } puts("");

  DSU dsu(W.size());
  vector<int> wcnt(W.size(), 0);
  vector<int> wsum(W.size(), 0);
  vector<int> wcon(W.size(), 0);
  vector<int> wpre(W.size(), 0);
  vector<int> wmin(W.size(), 0);
  vector<pair<int, int>> wlow(W.size(), {0, 0});

  int sumD = 0;

  for(int i = 0; i < W.size(); i++) {
    wmin[i] = INF;
    for(auto d: D[W[i]]) {
      wcnt[i]++;
      wsum[i] += d;
      cmin(wmin[i], d);
    }
    wpre[i] = wcnt[i] + (i > 0 ? wpre[i - 1] : 0);

    if(wcnt[i] == 1) {
      wlow[i] = {wmin[i], INF};
    } else {
      wlow[i] = {wmin[i], wmin[i]};
    }

    wcon[i] = wsum[i];
    // Sacrifice
    if(wcnt[i] % 2 == 1) {
      wcon[i] -= wlow[i].first;
    } 

    sumD += wcon[i];
  }

  vector<pair<int, int>> P;
  for(int i = 1; i < W.size(); i++) {
    P.push_back({W[i] - W[i - 1], i});
    if(i > 1) P.push_back({W[i] - W[i - 2], -i});
  }
  sort(begin(P), end(P));

  vector<int> QI;
  for(int i = 0; i < Q; i++) QI.push_back(i);
  sort(begin(QI), end(QI), [&](int i, int j) { return E[i] < E[j]; });


  std::vector<long long> R(Q, 0);

  int pi = 0;

  for(int qi: QI) {
    int e = E[qi];

    // printf("qi=%d e=%d \n", qi, e);

    // Expand
    while(pi < P.size() && P[pi].first <= e) {
      int wi = abs(P[pi].second);
      int delta = P[pi].second < 0 ? 2 : 1;
      int l, r;
      // We know these are connected already, just 
      if(delta == 2) {
        // printf("delta = %d, [%d, %d]\n", delta, wi-2, wi);
        l = dsu.find(wi);
        // Reset
        sumD -= wcon[l];

        int pre = wpre[wi - 2] - (l > 0 ? wpre[l - 1] : 0);

        // Need to check against raw size
        if(D[W[wi - 1]].size() == 1) {
          if(pre % 2 == 0) {
            cmin(wlow[l].second, wmin[wi - 1]);
          } else {
            cmin(wlow[l].first, wmin[wi - 1]);
          }
        } else {
          cmin(wlow[l].first, wmin[wi - 1]);
          cmin(wlow[l].second, wmin[wi - 1]);
        }
      } else { // Here we connect them together
        l = dsu.find(wi-1);
        r = dsu.find(wi);

        // Reset
        sumD -= wcon[l];
        sumD -= wcon[r];

        wsum[l] += wsum[r];

        int lcnt = wcnt[l];
        int rcnt = wcnt[r];

        if(lcnt % 2 == 0) {
          cmin(wlow[l].first, wlow[r].first);
          cmin(wlow[l].second, wlow[r].second);
        } else {
          cmin(wlow[l].first, wlow[r].second);
          cmin(wlow[l].second, wlow[r].first);
        }

        wcnt[l] = lcnt + rcnt;
        dsu.f[r] = l;
      }

      if(wcnt[l] % 2 == 0) {
        wcon[l] = wsum[l];
      } else {
        wcon[l] = wsum[l] - wlow[l].first;
      }
      sumD += wcon[l];

      // printf("l = %d wcnt = %d low = [%d, %d] con=%d\n", l, wcnt[l], wlow[l].first, wlow[l].second, wcon[l]);

      // END
      pi++;
    }

    // printf("sumA=%d sumD=%d\n", sumA, sumD);
    R[qi] = sumA - sumD;
  }

  return R;
}

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