Submission #897889

#	Time	Username	Problem	Language	Result	Execution time	Memory
897889		AdamGS	Garden (JOI23_garden)	C++17	100 / 100	1475 ms	232732 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;
  int mi_x=d, ma_x=0, mi_y=d, ma_y=0;
  vector<int>X, Y;
  rep(i, n) {
    int a, b;
    cin >> a >> b; 
    X.pb(a);
    Y.pb(b);
    wiersz[a]=wiersz[a+d]=1;
    kolumna[b]=kolumna[b+d]=1;
  }
  int ans=d*d;
  if(X.size()>1) {
    sort(all(X));
    rep(i, (int)X.size()-1) ans=min(ans, (d-(X[i+1]-X[i]+1)+2)*d);
    ans=min(ans, (d-(d-X.back()+X[0]+1)+2)*d);
  } else ans=d;
  if(Y.size()>1) {
    sort(all(Y));
    rep(i, (int)Y.size()-1) ans=min(ans, (d-(Y[i+1]-Y[i]+1)+2)*d);
    ans=min(ans, (d-(d-Y.back()+Y[0]+1)+2)*d);
  } else ans=d;
  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;
  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';
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:27:7: warning: unused variable 'mi_x' [-Wunused-variable]
   27 |   int mi_x=d, ma_x=0, mi_y=d, ma_y=0;
      |       ^~~~
garden.cpp:27:15: warning: unused variable 'ma_x' [-Wunused-variable]
   27 |   int mi_x=d, ma_x=0, mi_y=d, ma_y=0;
      |               ^~~~
garden.cpp:27:23: warning: unused variable 'mi_y' [-Wunused-variable]
   27 |   int mi_x=d, ma_x=0, mi_y=d, ma_y=0;
      |                       ^~~~
garden.cpp:27:31: warning: unused variable 'ma_y' [-Wunused-variable]
   27 |   int mi_x=d, ma_x=0, mi_y=d, ma_y=0;
      |                               ^~~~

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