Submission #925362

#	Time	Username	Problem	Language	Result	Execution time	Memory
925362		esomer	Garden (JOI23_garden)	C++17	6 / 100	3030 ms	4184 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);
	}
};

bool isInside(int lx, int rx, int ly, int ry, pair<int, int> p){
	if(lx <= p.first && rx >= p.first && ly <= p.second && ry >= p.second) return true;
	return false;
}

int brute(int N, int M, int D, vector<pair<int, int>>& A, vector<pair<int, int>>& B){
    int ans = 2e9;
    for(int lx = 0; lx < 2 * D; lx++){
        for(int rx = lx; rx < 2 * D; rx++){
            for(int ly = 0; ly < 2 * D; ly++){
                for(int ry = ly; ry < 2 * D; ry++){
                    bool gd = true;
                    for(int i = 0; i < N; i++){
                        if(!(isInside(lx, rx, ly, ry, A[i]) || isInside(lx, rx, ly, ry, {A[i].first+D, A[i].second}) ||
                            isInside(lx, rx, ly, ry, {A[i].first, A[i].second+D}) || isInside(lx, rx, ly, ry, {A[i].first + D, A[i].second + D}))){
                            gd = false;
                        }
                    }
                    for(int i = 0; i < M; i++){
                        if(!((ly <= B[i].second && B[i].second <= ry) || 
                            (ly <= B[i].second + D && B[i].second + D <= ry) ||
                            (lx <= B[i].first && B[i].first <= rx) ||
                            (lx <= B[i].first + D && B[i].first + D <= rx))){
                            gd = false;
                        }
                    }
                    if(gd) ans = min(ans, (rx - lx + 1) * (ry - ly + 1));
                }
            }
        }
    }
    return ans;
}

 
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;
	cout << brute(N, M, D, A, B) << "\n";
	// 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: 6 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25