Submission #1182246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182246		noyancanturk	Garden (JOI23_garden)	C++20	75 / 100	3093 ms	7492 KiB

garden

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;

const int lim=5005;

struct{
  int parent[lim],sz[lim];
  vector<int>guys;
  void init(){
    for(int i=0;i<lim;i++){
      parent[i]=i;
      sz[i]=1;
    }
  }
  int find(int i){
    if(i==parent[i])return i;
    return parent[i]=find(parent[i]);
  }
  int unite(int i,int j){
    i=find(i),j=find(j);
    if(i==j)return 0;
    guys.pb(i);guys.pb(j);
    parent[i]=j;
    sz[j]+=sz[i];
    return 1;
  }
  void tralilitralala(){
    for(int i:guys)parent[i]=i,sz[i]=1;
    guys.clear();
  }
}dsu;

int havex[lim]{},havey[lim]{};
int parx[lim],pary[lim];
int lenx[lim]{},leny[lim]{};
vector<int>in[lim];

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m,D;
  cin>>n>>m>>D;
  for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    havex[x]=1;
    havey[y]=1;
  }
  int c[m],d[m];
  for(int i=0;i<m;i++){
    cin>>c[i]>>d[i];
    if(havex[c[i]]||havey[d[i]]){
      i--;
      m--;
    }
  }
  for(int i=0;i<D;i++){
    parx[i]=i;
    pary[i]=i;
  }
  for(int i=0;i<D;i++){
    if(!havex[i]&&!havex[(i+D-1)%D])parx[i]=parx[(i+D-1)%D];
    if(!havey[i]&&!havey[(i+D-1)%D])pary[i]=pary[(i+D-1)%D];
  }
  for(int i=0;i<D;i++){
    if(!havex[i]&&!havex[(i+D-1)%D])parx[i]=parx[(i+D-1)%D];
    if(!havey[i]&&!havey[(i+D-1)%D])pary[i]=pary[(i+D-1)%D];
  }
  for(int i=0;i<D;i++){
    lenx[parx[i]]++;
    leny[pary[i]]++;
  }
  for(int i=0;i<m;i++){
    in[c[i]].pb(d[i]);
  }
  int ans=D*D;
  int beg=-1;
  for(int x=0;x<D;x++){
    if(havex[x]||parx[x]!=x)continue;
    beg=x;
    ans=min(ans,D*(D-lenx[x]));
  }
  for(int y=0;y<D;y++){
    if(havey[y]||pary[y]!=y)continue;
    ans=min(ans,D*(D-leny[y]));
  }
  dsu.init();
  if(beg!=-1)for(int x=beg;x!=(beg+D-1)%D;x=(x+1)%D){
    if(havex[x])continue;
    int ok[D]{};
    for(int y=0;y<D;y++){
      ok[y]=!havey[y];
    }
    int left=0;
    for(int xind=x;!havex[xind];xind=(xind+D-1)%D){
      left++;
      vector<int>toput;
      for(int j:in[xind]){
        if(!ok[j])continue;
        toput.pb(j);
        ok[j]=0;
      }
      in[xind]=toput;
    }
    int maxdis=0;
    for(int y=0;y<D;y++){
      if(ok[y]){
        if(ok[(y+1)%D]){
          dsu.unite(y,(y+1)%D);
        }
        if(ok[(y+D-1)%D]){
          dsu.unite(y,(y+D-1)%D);
        }
        maxdis=max(maxdis,dsu.sz[dsu.find(y)]);
      }
    }
    ans=min(ans,(D-left)*(D-maxdis));
    for(int xind=parx[x];!havex[xind];xind=(xind+1)%D){
      left--;
      for(int y:in[xind]){
        ok[y]=1;
        if(ok[(y+1)%D]){
          dsu.unite(y,(y+1)%D);
        }
        if(ok[(y+D-1)%D]){
          dsu.unite(y,(y+D-1)%D);
        }
        maxdis=max(maxdis,dsu.sz[dsu.find(y)]);
      }
      ans=min(ans,(D-left)*(D-maxdis));
    }
    dsu.tralilitralala();
  }
  cout<<ans;
}

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