| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 925390 | esomer | Garden (JOI23_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
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();
mx = max(mx, 1);
if(zero[(i+n-1)%n]) unite(i, (i+n-1)%n);
if(zero[(i+1)%n]) unite(i, (i+1)%n);
}
};
signed 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";
}