Submission #1135394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135394		Zbyszek99	Building Skyscrapers (CEOI19_skyscrapers)	C++20	0 / 100	45 ms	1724 KiB

skyscrapers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vi graph[2001];
map<pii,int> point;
pii poz[2001];
bool used[2001];
bool can_out[2002][2002];
bool odw[2002];
int low[2002];
int pre[2002];
bool art[2002];
int cur_pre = 0;
int max_x = -1;
int max_y = -1;

vector<pii> dir1 = {{0,1},{0,-1},{1,0},{1,-1},{1,1},{-1,-1},{-1,0},{-1,1}};
vector<pii> dir2 = {{0,1},{0,-1},{1,0},{-1,0}};

void dfs(int x,int y, int v)
{
    used[v] = true;
    forall(it,dir1)
    {
        if(point[{x+it.ff,y+it.ss}] != 0)
        {
            if(!used[point[{x+it.ff,y+it.ss}]])
            {
                dfs(x+it.ff,y+it.ss,point[{x+it.ff,y+it.ss}]);
            }
            graph[v].pb(point[{x+it.ff,y+it.ss}]);
        }
    }
}

void upd_out(int x, int y)
{
   // cout << x << " " << y << " xy\n";
    can_out[x][y] = true;
    if(used[point[{x,y}]])
    {
        return;
    }
    forall(it,dir2)
    {
        if(x + it.ff >= 0 && x + it.ff <= max_x+2 && y + it.ss >= 0 && y + it.ss <= max_y+2)
        {
            if(!can_out[x+it.ff][y+it.ss])
            {
                upd_out(x+it.ff,y+it.ss);
            }
        }
    }
}

void calc_art(int v, int pop)
{
    odw[v] = 1;
    pre[v] = cur_pre++;
    low[v] = pre[v];
    int z = 0;
    int z2 = 0;
    forall(it,graph[v])
    {
        if(!used[it]) continue;
        z2++;
        if(odw[it])
        {
            if(it != pop)
            {
                low[v] = min(low[v],pre[it]);
            }
        }
        else
        {
            z++;
            calc_art(it,v);
            low[v] = min(low[v],low[it]);
            if(v != pop && low[it] >= pre[v]) art[v] = 1;
        }
    }
    if(v == pop)
    {
        if(z == 1 && z2 > 1)
        {
            art[v] = 1;
        }
    }
}


int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,t;
    cin >> n >> t;
    vi ans(n);
    vector<pii> points = {{0,0}};
    int min_x = 1e9+1;
    int min_y = 1e9+1; 
    rep2(i,1,n)
    {
        int x,y;
        cin >> x >> y;
        min_x = min(min_x,x);
        min_y = min(min_y,y);
        points.pb({x,y});
    }
    rep2(i,1,n)
    {
        points[i].ff -= min_x - 1;
        points[i].ss -= min_y - 1;
        point[points[i]] = i;
        poz[i] = points[i];
       // cout << points[i].ff << " " << points[i].ss << " p\n"; 
        max_x = max(max_x,points[i].ff);
        max_y = max(max_y,points[i].ss);
    }
    dfs(points[1].ff,points[1].ss,1);
    rep2(i,1,n)
    {
        if(!used[i])
        {
            cout << "NO\n";
            return 0;
        }
    }
    upd_out(0,0);
    for(int k = n-1; k >= 0; k--)
    {
      //  cout << k << " k\n";
        int v = 1;
        rep2(i,1,n) 
        {
            odw[i] = 0;
            art[i] = 0;
            if(used[i]) v = i;
        }
        cur_pre = 0;
        calc_art(v,v);
        for(int i = n; i >= 1; i--)
        {
        //    cout << i << " " << can_out[poz[i].ff][poz[i].ss] << " " << art[i] << " " << used[i] << " pot\n";
            if(can_out[poz[i].ff][poz[i].ss] && !art[i] && used[i])
            {
                ans[k] = i;
                used[i] = 0;
                upd_out(points[i].ff,points[i].ss);
                break;
            }
        }
    }
    cout << "YES\n";
    forall(it,ans) cout << it << "\n";
}

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