Submission #897882

#	Time	Username	Problem	Language	Result	Execution time	Memory
897882		AdamGS	Garden (JOI23_garden)	C++17	15 / 100	813 ms	233828 KiB

garden

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e4+7;
bitset<LIM>T[LIM];
vector<int>V[LIM];
int dp[LIM], wiersz[LIM], kolumna[LIM], F[LIM], ile[LIM];
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
  if(fnd(a)==fnd(b)) return;
  ile[fnd(a)]+=ile[fnd(b)];
  F[fnd(b)]=fnd(a);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m, d;
  cin >> n >> m >> d;
  rep(i, n) {
    int a, b;
    cin >> a >> b; 
    wiersz[a]=wiersz[a+d]=1;
    kolumna[b]=kolumna[b+d]=1;
  }
  rep(i, m) {
    int a, b;
    cin >> a >> b; 
    T[a][b]=T[a+d][b]=T[a][b+d]=T[a+d][b+d]=1;
  }
  rep(i, 2*d) rep(j, 2*d) if(wiersz[i] || kolumna[j]) T[i][j]=1;
  int ans=d*d;
  rep(i, 2*d) {
    rep(j, 2*d) if(!T[i][j]) dp[j]=min(dp[j]+1, d); else dp[j]=0;
    if(i<d-1) continue;
    rep(j, d) V[j+1].clear();
    rep(j, 2*d) {
      F[j]=-1;
      if(dp[j]) V[dp[j]].pb(j);
    }
    for(int j=d; j; --j) {
      for(auto l : V[j]) {
        F[l]=l;
        ile[l]=1;
        if(l && F[l-1]!=-1) uni(l, l-1);
        if(l+1<2*d && F[l+1]!=-1) uni(l+1, l);
        if(fnd(l)>=d-1) ans=min(ans, (d-j)*(d-ile[fnd(l)]));
      }
    }
  }
  cout << ans << '\n';
}

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