제출 #925362

#제출 시각아이디문제언어결과실행 시간메모리
925362esomerGarden (JOI23_garden)C++17
6 / 100
3030 ms4184 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...