Submission #825221

#	Time	Username	Problem	Language	Result	Execution time	Memory
825221		CSQ31	Garden (JOI23_garden)	C++17	75 / 100	3060 ms	596544 KiB

garden

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int par[5000],szz[5000];
bool p[5000],q[5000];
vector<int>g[5000],gr[5000];
int find(int x){
	if(par[x]==x)return x;
	return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(szz[a] > szz[b])swap(a,b);
	par[a] = b;
	szz[b]+=szz[a];
}
vector<int> del[5000][5000];
int main()
{
	owo
	int n,m,d,ans;
	cin>>n>>m>>d;
	ans = d*d;
	vector<int>cntq(d,0);
	
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		p[x] = 1;
		q[y] = 1;
	}
	int cntx = 0; //number of fixed points on the x axis
	for(int i=0;i<d;i++)cntx+=p[i];
	
	for(int i=0;i<m;i++){
		int r,s;
		cin>>r>>s;
		g[s].pb(r);
		gr[r].pb(s);
		cntq[s]++;
	}
	/*
	for(int i=0;i<d;i++){
		if(q[i])continue;
		sort(all(g[i]));
		int ss = sz(g[i]);
		if(ss==1){
			for(int j=0;j<d;j++)del[j][g[i][0]].pb(i);
		}else{
			for(int j=0;j<ss;j++){
				int l = g[i][j];
				int r = g[i][(j+1)%ss];
				int dis = r-l;
				if(dis<0)dis+=d;
				for(int k=1;k<=dis;k++){ //if we start from l+k we will remove i from the y axis at l
					del[(l+k)%d][l].pb(i);
					//cout<<(l+k)%d<<" "<<l<<" "<<i<<'\n';
				}
			}
		}
	}*/
	//cout<<"TES"<<'\n';
	for(int k=0;k<d;k++){
		for(int i=0;i<d;i++){
			par[i] = i;
			szz[i] = 1;
		}
		vector<int>tmp = cntq;
		int mx = 0;
		for(int i=0;i<d;i++){
			if(!q[i] && !q[(i+1)%d] && !tmp[i] && !tmp[(i+1)%d])unite(i,(i+1)%d);
		}
		for(int i=0;i<d;i++){
			if(!tmp[i] && !q[i])mx = max(mx,szz[i]);
		}
		
		int cnt = 0;
		for(int i=0;i<d;i++){
			int j = (i+k)%d;
			cnt+=p[j];
			/*
			for(int x:del[k][j]){
				int y = (x+d-1)%d;
				int z = (x+1)%d;
				if(!tmp[y])unite(x,y);
				if(!tmp[z])unite(x,z);
				tmp[x] = 0;
				mx = max(mx,szz[find(x)]);
			}*/
			for(int x:gr[j]){
				tmp[x]--;
				if(!tmp[x] && !q[x]){
					int y = (x+d-1)%d;
					int z = (x+1)%d;
					if(!tmp[y] && !q[y])unite(x,y);
					if(!tmp[z] && !q[z])unite(x,z);
					tmp[x] = 0;
					mx = max(mx,szz[find(x)]);
					
				}
			}
			//cout<<i<<" "<<k<<" "<<cnt<<" "<<mx<<'\n';
			if(cnt==cntx)ans = min(ans,(i+1)*(d-mx));
		}		
	}
	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