| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 623166 | Hanksburger | Fountain Parks (IOI21_parks) | 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 "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > vec[200005], edge;
vector<int> adj[200005], U, V, A, B;
map<pair<int, int>, bool> mp;
bool visited[20005];
queue<int> q;
int construct_roads(vector<int> X, vector<int> Y)
{
int N=X.size();
for (int i=0; i<N; i++)
vec[Y[i]].push_back({X[i], i});
bool ok=0;
for (int i=2; i<=2e5; i+=2)
{
if (vec[i].empty())
continue;
sort(vec[i].begin(), vec[i].end());
if (ok)
{
if (vec[i].size()==1)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first==vec[i][0].first)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
}
else if (vec[i].size()==2)
{
if (vec[i][0].first==2 && vec[i][1].first==4)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first<=4)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
if (vec[i-2][ind].first==2)
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
else
edge.push_back({vec[i-2][ind].second, vec[i][1].second});
}
else if (vec[i][0].first==4 && vec[i][1].first==6)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
if (vec[i-2][j].first>=4)
ind=j;
if (ind==-1)
return 0;
if (vec[i-2][ind].first==4)
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
else
edge.push_back({vec[i-2][ind].second, vec[i][1].second});
}
else
{
for (int k=0; k<2; k++)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first==vec[i][k].first)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
edge.push_back({vec[i-2][ind].second, vec[i][k].second});
}
}
}
else
{
if (vec[i-2].empty())
return 0;
if (vec[i-2][0].first==2)
edge.push_back({vec[i-2][0].second, vec[i][0].second});
else if (vec[i-2][0].first==4)
edge.push_back({vec[i-2][0].second, vec[i][1].second});
else
edge.push_back({vec[i-2][0].second, vec[i][2].second});
}
}
if (vec[i].size()==2)
{
if (vec[i][0].first+2==vec[i][1].first)
edge.push_back({vec[i][0].second, vec[i][1].second});
}
else if (vec[i].size()==3)
{
edge.push_back({vec[i][0].second, vec[i][1].second});
edge.push_back({vec[i][1].second, vec[i][2].second});
}
ok=1;
}
for (int i=0; i<edge.size(); i++)
{
int u=edge[i].first, v=edge[i].second;
adj[u].push_back(v);
adj[v].push_back(u);
U.push_back(u);
V.push_back(v);
if (X[u]==X[v])
{
if (mp[{X[u]-1, Y[u]+1}])
{
A.push_back(X[u]+1);
B.push_back(Y[u]+1);
mp[{X[u]+1, Y[u]+1}]=1;
}
else
{
A.push_back(X[u]-1);
B.push_back(Y[u]+1);
mp[{X[u]-1, Y[u]+1}]=1;
}
}
else
{
if (mp[{X[u]+1, Y[u]-1}])
{
A.push_back(X[u]+1);
B.push_back(Y[u]+1);
mp[{X[u]+1, Y[u]+1}]=1;
}
else
{
A.push_back(X[u]+1);
B.push_back(Y[u]-1);
mp[{X[u]+1, Y[u]-1}]=1;
}
}
}
q.push(0);
visited[0]=1;
while (!q.empty())
{
int u=q.front();
q.pop();
for (int v:adj[u])
{
if (!visited[v])
{
q.push(v);
visited[v]=1;
}
}
}
for (int i=0; i<n; i++)
if (!visited[i])
return 0;
build(U, V, A, B);
return 1;
}