Submission #1232854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232854		Tenis0206	Building Skyscrapers (CEOI19_skyscrapers)	C++20	54 / 100	3634 ms	989628 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

int n, T;
int r[nmax + 5], c[nmax + 5];

bool sel[nmax + 5];

map<pair<int,int>, int> t;

int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

void dfs_check(int nod)
{
    sel[nod] = true;
    int x = r[nod];
    int y = c[nod];
    for(int p=0; p<8; p++)
    {
        int xx = x + dx[p];
        int yy = y + dy[p];
        int son = t[ {xx, yy}];
        if(son == 0)
        {
            continue;
        }
        if(sel[son])
        {
            continue;
        }
        dfs_check(son);
    }
}

void solve1()
{
    int poz = 1;
    for(int i=1; i<=n; i++)
    {
        if(r[i] < r[poz] || (r[i] == r[poz] && c[i] < c[poz]))
        {
            poz = i;
        }
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> h;
    h.push({r[poz], c[poz]});
    sel[poz] = true;
    vector<int> rez;
    while(!h.empty())
    {
        int x = h.top().first;
        int y = h.top().second;
        int nod = t[ {x, y}];
        h.pop();
        rez.push_back(nod);
        for(int p=0; p<8; p++)
        {
            int xx = x + dx[p];
            int yy = y + dy[p];
            int son = t[ {xx, yy}];
            if(son == 0)
            {
                continue;
            }
            if(sel[son])
            {
                continue;
            }
            sel[son] = true;
            h.push({r[son], c[son]});
        }
    }
    cout<<"YES\n";
    for(auto it : rez)
    {
        cout<<it<<'\n';
    }
}

map<pair<int,int>,bool> w, reach, lib;
vector<pair<int,int>> lst;

bool used[nmax + 5];

int l[nmax + 5], lvl[nmax + 5];

bool crit[nmax + 5];

void bfs()
{
    queue<pair<int,int>> q;
    for(auto it : lst)
    {
        q.push(it);
    }
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int p=0; p<4; p++)
        {
            int xx = x + dx[p];
            int yy = y + dy[p];
            if(!w[ {xx, yy}] || reach[{xx, yy}])
            {
                continue;
            }
            if(t[ {xx, yy}] && !used[t[ {xx, yy}]])
            {
                reach[{xx, yy}] = true;
            }
            else
            {
                reach[{xx, yy}] = true;
                q.push({xx, yy});
            }
        }
    }
}

void dfs(int nod, int from = 0)
{
    crit[nod] = false;
    lvl[nod] = 1 + lvl[from];
    l[nod] = lvl[nod];
    int x = r[nod];
    int y = c[nod];
    sel[nod] = true;
    for(int p=0; p<8; p++)
    {
        int xx = x + dx[p];
        int yy = y + dy[p];
        int son = t[ {xx, yy}];
        if(son == 0 || used[son])
        {
            continue;
        }
        if(sel[son])
        {
            l[nod] = min(l[nod], lvl[son]);
        }
        else
        {
            dfs(son, nod);
            l[nod] = min(l[nod], l[son]);
            if(l[son] >= lvl[nod])
            {
                crit[nod] = true;
            }
        }
    }
}

void solve2()
{
    for(int i=1; i<=n; i++)
    {
        int x = r[i];
        int y = c[i];
        w[ {x, y}] = true;
        for(int p=0; p<8; p++)
        {
            int xx = x + dx[p];
            int yy = y + dy[p];
            if(t[ {xx, yy}])
            {
                continue;
            }
            w[ {xx, yy}] = true;

            lib[ {xx, yy}] = true;
            for(int j=xx; j<=xx+n; j++)
            {
                if(t[ {j, yy}])
                {
                    lib[ {xx, yy}] = false;
                    break;
                }
            }
            if(lib[ {xx, yy}])
            {
                continue;
            }

            lib[ {xx, yy}] = true;
            for(int j=xx-n; j<=xx; j++)
            {
                if(t[ {j, yy}])
                {
                    lib[ {xx, yy}] = false;
                    break;
                }
            }
            if(lib[ {xx, yy}])
            {
                continue;
            }

            lib[ {xx, yy}] = true;
            for(int j=yy; j<=yy+n; j++)
            {
                if(t[ {xx, j}])
                {
                    lib[ {xx, yy}] = false;
                    break;
                }
            }
            if(lib[ {xx, yy}])
            {
                continue;
            }

            lib[ {xx, yy}] = true;
            for(int j=yy-n; j<=yy; j++)
            {
                if(t[ {xx, j}])
                {
                    lib[ {xx, yy}] = false;
                    break;
                }
            }
            if(lib[ {xx, yy}])
            {
                continue;
            }
        }
        for(int p=0; p<8; p++)
        {
            int xx = x + dx[p];
            int yy = y + dy[p];
            if(lib[ {xx, yy}])
            {
                lst.push_back({xx, yy});
            }
        }
    }
    vector<int> rez(n + 1);
    for(int i=n; i>=1; i--)
    {
        reach.clear();
        bfs();
        for(int j=1; j<=n; j++)
        {
            sel[j] = false;
        }
        for(int j=1; j<=n; j++)
        {
            if(!used[j])
            {
                dfs(j);
                break;
            }
        }
        for(int val=n; val>=1; val--)
        {
            if(used[val] || crit[val] || !reach[ {r[val], c[val]}])
            {
                continue;
            }
            rez[i] = val;
            used[val] = true;
        }
    }
    cout<<"YES\n";
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i]<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif
    cin>>n;
    cin>>T;
    for(int i=1; i<=n; i++)
    {
        cin>>r[i]>>c[i];
        t[ {r[i], c[i]}] = i;
    }
    dfs_check(1);
    for(int i=1; i<=n; i++)
    {
        if(!sel[i])
        {
            cout<<"NO\n";
            return 0;
        }
        sel[i] = false;
    }
    if(T == 1)
    {
        solve1();
    }
    else
    {
        solve2();
    }
    return 0;
}

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