Submission #925356

#	Time	Username	Problem	Language	Result	Execution time	Memory
925356		esomer	Garden (JOI23_garden)	C++17	0 / 100	1424 ms	10996 KiB

garden

#include <bits/stdc++.h>
 
using namespace std;
 
struct DSU{
	vector<int> v;
	vector<bool> zero;
	int mx;
	void init(int n){
		v.assign(n, -1); mx = 0;
		zero.assign(n, false);
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	void unite(int x, int y){
		x = get(x); y = get(y);
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x; mx = max(mx, -v[x]);
	}
	void setZero(int i){
		zero[i] = true;
		int n = (int)v.size();
		if(zero[(i+n-1)%n]) unite(i, (i+n-1)%n);
		if(zero[(i+1)%n]) unite(i, (i+1)%n);
	}
};
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N, M, D; cin >> N >> M >> D;
	vector<pair<int, int>> A(N);
	for(int i = 0; i < N; i++) cin >> A[i].first >> A[i].second;
	vector<pair<int, int>> B(M);
	for(int i = 0; i < M; i++) cin >> B[i].first >> B[i].second;
	vector<int> cols(D, 0);
	vector<vector<int>> rows(2*D);
	for(int i = 0; i < N; i++){
		cols[A[i].first]++;
		rows[A[i].second].push_back(i);
	}
	for(int i = 0; i < M; i++){
		cols[B[i].first]++;
		rows[B[i].second].push_back(N+i);
	}
	int ans = D * D;
	for(int startRow = 0; startRow < D; startRow++){
		int lft = N;
		vector<int> col = cols;
		DSU UF; UF.init(D);
		for(int i = 0; i < D; i++){
			if(col[i] == 0) UF.setZero(i);
		}
		for(int r = startRow; r < startRow + D; r++){
			for(int i : rows[r]){
				if(i < N){
					lft--;
				}else{
					i -= N;
					col[B[i].first]--;
					if(col[B[i].first] == 0) UF.setZero(B[i].first);
				}
			}
			if(lft > 0) continue;
			ans = min(ans, (r - startRow + 1) * (D - UF.mx));
		}
		for(int i : rows[startRow]){
			rows[startRow + D].push_back(i);
		}
	}
	cout << ans << "\n";
}

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