| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1095980 | yoav_s | Building Skyscrapers (CEOI19_skyscrapers) | 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;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
p getParent(p cur, vvp &dsuParent)
{
if (dsuParent[cur.f][cur.s] == cur) return cur;
return dsuParent[cur.f][cur.s] = getParent(dsuParent[cur.f][cur.s], dsuParent);
}
vp getNeighbors(p pos, ll maxX, ll maxY)
{
vp neighbors; ll i = pos.f; ll j = pos.s;
if (i - 1 >= 0)
{
neighbors.eb(i - 1, j);
}
if (i + 1 < maxX)
{
neighbors.eb(i + 1, j);
}
if (j - 1 >= 0)
{
neighbors.eb(i, j - 1);
}
if (j + 1 < maxY)
{
neighbors.eb(i, j + 1);
}
return neighbors;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, t;
cin >> n >> t;
vp cells(n);
for (ll i= 0; i < n; i++) cin >> cells[i].f >> cells[i].s;
v relevantX, relevantY;
for (ll i = 0; i < n; i++)
{
relevantX.pb(cells[i].f - 1);
relevantX.pb(cells[i].f);
relevantX.pb(cells[i].f + 1);
relevantY.pb(cells[i].s - 1);
relevantY.pb(cells[i].s);
relevantY.pb(cells[i].s + 1);
}
sort(all(relevantX)); sort(all(relevantY));
relevantX.erase(unique(all(relevantX)), relevantX.end()); relevantY.erase(unique(all(relevantY)), relevantY.end());
map<ll, ll> xShrink;
map<ll, ll> yShrink;
for (ll i = 0; i < relevantX.size(); i++) xShrink[relevantX[i]] = i + 1;
for (ll i = 0; i < relevantY.size(); i++) yShrink[relevantY[i]] = i + 1;
for (ll i = 0; i < n; i++) cells[i] = p(xShrink[cells[i].f], yShrink[cells[i].s]);
ll maxX = relevantX.size() + 2, maxY = relevantY.size() + 2;
vv occupied(maxX, v(maxY, -1));
for (ll i = 0; i < n; i++) occupied[cells[i].f][cells[i].s] = i;
set<ll> remaining;
auto cmp = [&cells](ll i, ll j){return cells[i] > cells[j];};
if (rand() % 2) cmp = [&cells](ll i, ll j){return cells[i] > cells[j];};
set<ll, decltype(cmp)> available(cmp);
for (ll i = 0; i < n; i++) remaining.insert(i);
v order;
vb possible(n, false);
vv adjacentStructures(n);
for (ll i = 0; i < n; i++)
{
for (ll j = i + 1; j < n; j++)
{
if (abs(cells[i].f - cells[j].f) <= 1 && abs(cells[i].s - cells[j].s) <= 1)
{
adjacentStructures[i].pb(j);
adjacentStructures[j].pb(i);
}
}
}
vb visited(n, false);
stack<ll> dfs; dfs.push(0);
ll cnt = 0;
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (visited[top]) continue;
visited[top] = true; cnt++;
for (ll x : adjacentStructures[top]) dfs.push(x);
}
if (cnt != n)
{
cout << "NO\n";
return 0;
}
vvp dsuParent(maxX, vp(maxY));
for (ll i = 0; i < maxX; i++) for (ll j = 0; j < maxY; j++) dsuParent[i][j] = p(i, j);
vv dsuSize(maxX, v(maxY, 1));
for (ll i = 0; i < maxX; i++)
{
for (ll j = 0; j < maxY; j++)
{
if (occupied[i][j] != -1) continue;
vp neighbors = getNeighbors(p(i, j), maxX, maxY);
for (auto x : neighbors)
{
if (occupied[x.f][x.s] != -1) continue;
p p1 = getParent(p(i, j), dsuParent), p2 = getParent(x, dsuParent);
if (p1 == p2) continue;
if (dsuSize[p1.f][p1.s] > dsuSize[p2.f][p2.s]) swap(p1,p2);
dsuParent[p1.f][p1.s] = p2;
dsuSize[p2.f][p2.s] += dsuSize[p1.f][p1.s];
}
}
}
for (ll i = 0; i < n; i++)
{
vp neighbors = getNeighbors(cells[i], maxX, maxY);
bool hasNeighbor = false;
p expected = getParent(p(0, 0), dsuParent);
for (auto y : neighbors)
{
if (getParent(y, dsuParent) == expected) hasNeighbor = true;
}
if (hasNeighbor) available.insert(i);
}
for (ll i = n - 1; i >= 0; i--)
{
bool done = false;
for (ll x : available)
{
vp neighbors = getNeighbors(cells[x], maxX, maxY);
if (i > 1)
{
vb visited(n, false);
auto ptr = remaining.begin();
if (*ptr == x) ptr++;
ll start = *ptr;
stack<ll> dfs; dfs.push(start);
ll cnt = 0;
while (!dfs.empty())
{
auto top = dfs.top();
dfs.pop();
if (remaining.count(top) == 0 || top == x || visited[top]) continue;
visited[top] = true; cnt++;
for (ll x : adjacentStructures[top]) dfs.push(x);
}
if (cnt != remaining.size() - 1)
{
continue;
}
}
occupied[cells[x].f][cells[x].s] = -1;
for (auto y : neighbors)
{
if (occupied[y.f][y.s] == -1)
{
p p1 = getParent(y, dsuParent), p2 = getParent(cells[x], dsuParent);
if (p1 == p2) continue;
if (dsuSize[p1.f][p1.s] > dsuSize[p2.f][p2.s]) swap(p1,p2);
dsuParent[p1.f][p1.s] = p2;
dsuSize[p2.f][p2.s] += dsuSize[p1.f][p1.s];
}
}
p expect = getParent(p(0, 0), dsuParent);
p par = getParent(cells[x], dsuParent);
if (par == expect)
{
for (auto y : neighbors)
{
if (occupied[y.f][y.s] == -1)
{
vp nei = getNeighbors(y, maxX, maxY);
for (auto z : nei)
{
if (occupied[z.f][z.s] != -1) available.insert(occupied[z.f][z.s]);
}
}
else
{
available.insert(occupied[y.f][y.s]);
}
}
}
remaining.erase(x);
available.erase(x);
order.pb(x);
done = true;
break;
}
assert(done);
}
reverse(all(order));
cout << "YES\n";
for (ll x : order) cout << x + 1 << "\n";
return 0;
}