Submission #826284

#	Time	Username	Problem	Language	Result	Execution time	Memory
826284		erray	Garden (JOI23_garden)	C++17	100 / 100	2320 ms	7128 KiB

garden

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/day2/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct DSU {
  vector<int> link;
  vector<int> sz;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
    sz.resize(n, 1);
  }
  int get(int v) {
    return link[v] = (link[v] == v ? v : get(link[v])); 
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    sz[x] += sz[y];
    return true;
  }
  int size(int x) {
    return sz[get(x)];
  }
};

int main() {
  int N, M, D;
  cin >> N >> M >> D;
  vector<bool> X(D), Y(D);
  for (int i = 0; i < N; ++i) {
    int P, Q;
    cin >> P >> Q;
    X[P] = true;
    Y[Q] = true;
  }
  vector<vector<int>> link(D);
  vector<int> rem(D, -1);
  for (int i = 0; i < M; ++i) {
    int R, S;
    cin >> R >> S;
    if (!Y[S]) {
      rem[S] = max(rem[S], R);
      link[R].push_back(S);
    }
  }
  debug(X, Y, rem, link);
  int ans = D * D;
  for (int l = 0; l < D; ++l) {
    int X_need = accumulate(X.begin(), X.end(), 0);
    vector<bool> out(D, false);
    DSU comps(D);
    int gap = 0;
    auto Rem = [&](int x) {
      for (auto d : {-1, 1}) {
        int go = (x + d + D) % D;
        if (out[go]) {
          comps.unite(x, go);
        }
      }
      out[x] = true;
      gap = max(gap, comps.size(x));
    };
    vector<vector<int>> rt(D);
    for (int i = 0; i < D; ++i) {
      if (rem[i] != -1) {
        rt[rem[i]].push_back(i);
      } else if (!Y[i]) {
        Rem(i);
      }
    }
    for (int s = 1; s <= D; ++s) {
      int add = (l + s - 1) % D;
      X_need -= X[add];
      for (auto y : rt[add]) {
        Rem(y);
      }
      if (X_need == 0) {
        ans = min(ans, s * (D - gap));
      }
    }
    for (auto x : link[l]) {
      rem[x] = l;
    }
  }
  cout << ans << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25