Submission #1182255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182255		noyancanturk	Garden (JOI23_garden)	C++20	75 / 100	3095 ms	26440 KiB

garden

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=5005;

struct{
  int parent[lim],sz[lim];
  int guys[lim];
  int szz=0;
  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;
    if(parent[i]==i&&sz[i]==1)guys[szz++]=i;
    if(parent[j]==j&&sz[j]==1)guys[szz++]=j;
    parent[i]=j;
    sz[j]+=sz[i];
    return 1;
  }
  void tralilitralala(){
    while(szz){
      --szz;
      parent[guys[szz]]=guys[szz];
      sz[guys[szz]]=1;
    }
  }
}dsu;

int havex[lim]{},havey[lim]{};
int parx[lim],pary[lim];
int lenx[lim]{},leny[lim]{};
int in[lim][lim],szs[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]][szs[c[i]]++]=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++;
      int sss=0;
      for(int i=0;i<szs[xind];i++){
        if(!ok[in[xind][i]]){
          in[xind][i]=in[xind][szs[xind]-1];
          szs[xind]--;
          i--;
        }else ok[in[xind][i]]=0;
      }
    }
    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 j=0;j<szs[xind];j++){
        int y=in[xind][j];
        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