| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1188557 | alexdd | Garden (JOI23_garden) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n,m,d;
vector<int> onpoz[5005][5005];
int poz[500005],cntactive;
bool active[500005];
pair<int,int> special[500005];
int goup[10005],goleft[10005];
int worst[10005];
vector<int> with_worst[10005];
int siz[10005],father[10005];
void init()
{
for(int i=0;i<=d;i++)
father[i]=i,siz[i]=1;
}
int gas(int x)
{
if(father[x]!=x)
father[x] = gas(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = gas(x);
y = gas(y);
if(x==y)
return;
if(siz[x] < siz[y])
swap(x,y);
father[y] = x;
siz[x] += siz[y];
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>d;
vector<int> base;
for(int i=0;i<n;i++)
{
int p,q;
cin>>p>>q;
onpoz[p][q].push_back(i);
base.push_back(q);
}
for(int i=0;i<m;i++)
{
int p,q;
cin>>p>>q;
special[i] = {p,q};
}
int rez = d*d;
multiset<int> cv;
for(int jos=0;jos<2*d;jos++)
{
for(int i=0;i<d;i++)
{
for(int x:onpoz[jos%d][i])
{
if(!active[x])
{
cntactive++;
active[x] = 1;
}
else
{
cv.erase(cv.find(poz[x]));
}
poz[x] = jos;
cv.insert(poz[x]);
}
}
if(cntactive == n)
{
int minlin=jos;
if(!cv.empty()) minlin = min(minlin, *cv.begin());
goup[jos] = minlin;
}
else
goup[jos] = -1;
}
cv.clear();
cntactive=0;
for(int x=0;x<n;x++)
active[x]=0;
for(int jos=0;jos<2*d;jos++)
{
for(int i=0;i<d;i++)
{
for(int x:onpoz[i][jos%d])
{
if(!active[x])
{
cntactive++;
active[x] = 1;
}
else
{
cv.erase(cv.find(poz[x]));
}
poz[x] = jos;
cv.insert(poz[x]);
}
}
if(cntactive == n)
{
int minlin=jos;
if(!cv.empty()) minlin = min(minlin, *cv.begin());
goleft[jos] = minlin;
}
else
goleft[jos] = -1;
}
for(int x:base)
worst[x] = -1;
for(int jos=d;jos<2*d;jos++)
{
s = inits;
rezs = initrez;
for(int i=0;i<2*d;i++)
with_worst[i].clear();
for(int i=0;i<d;i++)
if(worst[i] != -1)
worst[i] = jos+1;
for(int x=0;x<m;x++)
{
if(special[x].first + d <= jos)
{
worst[special[x].second] = min(worst[special[x].second], special[x].first + d);
}
else
{
worst[special[x].second] = min(worst[special[x].second], special[x].first);
}
}
for(int i=0;i<d;i++)
if(worst[i] != -1)
with_worst[worst[i]].push_back(i);
init();
int mxm=1;
for(int sus=jos+1;sus>=jos-d+1;sus--)
{
for(int x:with_worst[sus])
{
if(x-1>=0 && worst[x-1] >= sus) unite(x,x-1);
if(x+1<d && worst[x+1] >= sus) unite(x,x+1);
mxm = max(mxm, siz[gas(x)]);
}
if(sus<=goup[jos])
{
rez = min(rez, (jos-sus+1) * (d - mxm));
int sum=0;
if(worst[0] >= sus)
sum += siz[gas(0)];
if(worst[d-1] >= sus)
sum += siz[gas(d-1)];
assert(sum < d);
rez = min(rez, (jos-sus+1) * (d - sum));
}
}
}
cout<<rez;
return 0;
}
/*
2 1 5
1 4
2 2
0 0
patratele se repeta din d in d
obs: o sa existe tot timpu o solutie care are fiecare latura <d
*/