Submission #1092726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092726		raphaelp	Building Skyscrapers (CEOI19_skyscrapers)	C++14	100 / 100	2184 ms	107928 KiB

skyscrapers

#include <bits/stdc++.h>
using namespace std;
void dfs(int x, vector<vector<int>> &AR, vector<int> &occ, int &nb)
{
    if (occ[x])
        return;
    nb--;
    occ[x] = 1;
    for (int i = 0; i < AR[x].size(); i++)
    {
        dfs(AR[x][i], AR, occ, nb);
    }
}
class UnionFind
{
private:
    vector<int> p;

public:
    UnionFind(int x)
    {
        p.assign(x, 0);
        for (int i = 0; i < x; i++)
            p[i] = i;
    }
    int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }
    void merge(int a, int b)
    {
        int x = find(a), y = find(b);
        if (x == y)
            return;
        p[x] = y;
    }
};
int main()
{
    int N, T;
    cin >> N >> T;
    map<pair<int, int>, int> M;
    vector<pair<int, int>> Tab;
    vector<vector<int>> AR, AR2;
    vector<pair<int, int>> trans1 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, trans2 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    int buff = 0;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        Tab.push_back({x, y});
        M[{x, y}] = buff++;
        AR.push_back({});
        AR2.push_back({});
        for (int j = 0; j < 4; j++)
            if (M.count({x + trans1[j].first, y + trans1[j].second}))
            {
                AR[i].push_back(M[{x + trans1[j].first, y + trans1[j].second}]);
                AR[M[{x + trans1[j].first, y + trans1[j].second}]].push_back(i);
            }
        for (int j = 0; j < 8; j++)
            if (M.count({x + trans2[j].first, y + trans2[j].second}))
            {
                AR2[i].push_back(M[{x + trans2[j].first, y + trans2[j].second}]);
                AR2[M[{x + trans2[j].first, y + trans2[j].second}]].push_back(i);
            }
    }
    vector<int> ans, occ(N);
    int nb = N;
    dfs(0, AR2, occ, nb);
    if (nb)
    {
        cout << "NO" << '\n';
        return 0;
    }
    pair<int, int> minn = {1000000010, 0};
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            int x = Tab[i].first + trans2[j].first, y = Tab[i].second + trans2[j].second;
            if (M.count({x, y}) == 0)
            {
                M[{x, y}] = buff++;
                minn = min(minn, {x, y});
                Tab.push_back({x, y});
                AR.push_back({});
                AR2.push_back({});
                for (int k = 0; k < 4; k++)
                    if (M.count({x + trans1[k].first, y + trans1[k].second}))
                    {
                        AR[buff - 1].push_back(M[{x + trans1[k].first, y + trans1[k].second}]);
                        AR[M[{x + trans1[k].first, y + trans1[k].second}]].push_back(buff - 1);
                    }
            }
        }
    }
    UnionFind UF(buff);
    occ.assign(buff, 0);
    occ[M[minn]] = 1;
    queue<int> Q;
    Q.push(M[minn]);
    vector<int> done(N);
    priority_queue<int> next;
    for (int i = N; i < buff; i++)
    {
        for (int j = 0; j < AR[i].size(); j++)
        {
            if (AR[i][j] < N)
                continue;
            UF.merge(i, AR[i][j]);
        }
    }
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < AR[x].size(); i++)
        {
            if (occ[AR[x][i]])
                continue;
            occ[AR[x][i]] = 1;
            if (AR[x][i] >= N)
                Q.push(AR[x][i]);
            else
                next.push(AR[x][i]);
        }
    }
    while (!next.empty())
    {
        int x = next.top();
        next.pop();
        if (done[x])
            continue;
        vector<int> count = {M[{Tab[x].first - 1, Tab[x].second - 1}], M[{Tab[x].first - 1, Tab[x].second}], M[{Tab[x].first - 1, Tab[x].second + 1}], M[{Tab[x].first, Tab[x].second + 1}], M[{Tab[x].first + 1, Tab[x].second + 1}], M[{Tab[x].first + 1, Tab[x].second}], M[{Tab[x].first + 1, Tab[x].second - 1}], M[{Tab[x].first, Tab[x].second - 1}]};
        for (int i = 0; i < 8; i++)
            count[i] = ((count[i] >= N || done[count[i]]) ? 0 : 1);
        int u = M[{Tab[x].first - 1, Tab[x].second}], d = M[{Tab[x].first + 1, Tab[x].second}], l = M[{Tab[x].first, Tab[x].second - 1}], r = M[{Tab[x].first, Tab[x].second + 1}];
        if ((u >= N || done[u]) && (d >= N || done[d]) && UF.find(u) == UF.find(d))
        {
            if (count[0] + count[6] + count[7] && count[2] + count[3] + count[4])
                continue;
        }
        if ((l >= N || done[l]) && (r >= N || done[r]) && UF.find(l) == UF.find(r))
        {
            if (count[0] + count[1] + count[2] && count[4] + count[5] + count[6])
                continue;
        }
        if ((u >= N || done[u]) && (l >= N || done[l]) && UF.find(u) == UF.find(l))
        {
            if (count[0] && count[2] + count[3] + count[4] + count[5] + count[6])
                continue;
        }
        if ((u >= N || done[u]) && (r >= N || done[r]) && UF.find(u) == UF.find(r))
        {
            if (count[0] + +count[4] + count[5] + count[6] + count[7] && count[2])
                continue;
        }
        if ((l >= N || done[l]) && (d >= N || done[d]) && UF.find(l) == UF.find(d))
        {
            if (count[0] + count[1] + count[2] + count[3] + count[4] && count[6])
                continue;
        }
        if ((r >= N || done[r]) && (d >= N || done[d]) && UF.find(r) == UF.find(d))
        {
            if (count[0] + count[6] + count[7] + count[1] + count[2] && count[4])
                continue;
        }

        ans.push_back(x);
        done[x] = 1;
        for (int i = 0; i < AR[x].size(); i++)
        {
            if (AR[x][i] >= N || done[AR[x][i]])
                UF.merge(x, AR[x][i]);
        }
        Q.push(x);
        while (!Q.empty())
        {
            int y = Q.front();
            Q.pop();
            for (int i = 0; i < AR[y].size(); i++)
            {
                if (occ[AR[y][i]])
                    continue;
                occ[AR[y][i]] = 1;
                if (AR[y][i] >= N)
                    Q.push(AR[y][i]);
                else
                    next.push(AR[y][i]);
            }
        }
        for (int i = 0; i < AR2[x].size(); i++)
        {
            if (AR2[x][i] >= N || done[AR2[x][i]] || occ[AR2[x][i]] == 0)
                continue;
            next.push(AR2[x][i]);
        }
    }
    cout << "YES" << '\n';
    for (int i = N - 1; i >= 0; i--)
    {
        cout << ans[i] + 1 << '\n';
    }
}

Compilation message (stderr)

skyscrapers.cpp: In function 'void dfs(int, std::vector<std::vector<int> >&, std::vector<int>&, int&)':
skyscrapers.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int j = 0; j < AR[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
skyscrapers.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int i = 0; i < AR[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~
skyscrapers.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for (int i = 0; i < AR[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~
skyscrapers.cpp:179:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             for (int i = 0; i < AR[y].size(); i++)
      |                             ~~^~~~~~~~~~~~~~
skyscrapers.cpp:190:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |         for (int i = 0; i < AR2[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 10 / 10
• Subtask 7: 19 / 19