Submission #779445

#	Time	Username	Problem	Language	Result	Execution time	Memory
779445		definitelynotmee	Building Skyscrapers (CEOI19_skyscrapers)	C++17	100 / 100	1657 ms	117060 KiB

skyscrapers

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
 
    int n;
    cin >> n;
    int t;
    cin >> t;
 
    vector<pii> v(n);
 
    for(auto & i : v)
        cin >> i.ff >> i.ss;
 
    map<pii,int> mp;
 
    for(int i = 0; i < n; i++){
        mp[{v[i].ff,v[i].ss}] = i;
    }
 
    vector<int> pai(n);
    iota(all(pai),0);
    int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
    int dx2[]{-1,-1,-1,0,1,1,1,0}, dy2[]{-1,0,1,1,1,0,-1,-1};
 
    auto find =[&](int id, auto f) -> int {
        if(pai[id] == id)
            return id;
        return pai[id] = f(pai[id],f);
    };
    int cmp = n;
    auto onion =[&](int a, int b) -> void {
        a = find(a,find);
        b = find(b,find);
        if(a != b){
            pai[a] = b;
            cmp--;
        }
 
    };
    vector<int> deg(n);
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 8; j++){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            if(mp.count({xi,yi})){
                onion(i,mp[{xi,yi}]);
                deg[i]++;
                // cout << i << "++\n";
                // cout << mp[{xi,yi}] << "++\n";
            }
        }
    }
 
    if(cmp > 1){
        cout << "NO\n";
        return 0;
    }
 
 
    t = n;
    
    vector<array<int,8>> adj(v.size(),array<int,8>({}));


    for(int i = 0; i < n; i++){
        for(int j = 0; j < 8; j++){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            if(!mp.count({xi,yi})){
                mp[{xi,yi}] = t++;
                v.push_back({xi,yi});
            }
            adj[i][j] = mp[{xi,yi}];
        }
    }
    adj.resize(t,array<int,8>({}));

    pai = vector<int>(t);
    iota(all(pai),0);
 
    for(int i = n; i < t; i++){
        for(int j = 1; j < 8; j+=2){
            int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
            
            if(mp.count({xi,yi})){
                const int curval = mp[{xi,yi}];

                adj[i][j] = curval;
                
                if(curval >= n)
                    onion(i,adj[i][j]);
            } else adj[i][j] = -1;
        }
    }
 
 
 
 
    vector<int> check(n);
 
    priority_queue<int> pq;
 
    vector<int> passed(v.size());
    vector<int> reached(n);
    
    
    auto dfs =[&](int id, auto dfs) -> void {
        passed[id] = 1;
        for(int i = 1; i < 8; i+=2){
            int curval = adj[id][i];
            if(curval != -1 && !passed[curval]){
 
                if(curval >= n){
                    dfs(curval,dfs);
                } else {
                    if(!check[curval]){
                        check[curval] = 1;
                        reached[curval] = 1;
                        pq.push(curval);
                    }
                }
            }
        }
 
    };
 
    int mn = 0;
 
    for(int i = 1; i < n; i++){
        mn = min(mn,i,[&](int a, int b){
            return v[a].ff < v[b].ff;
        });
    }
    dfs(mp[{v[mn].ff-1,v[mn].ss}],dfs);
    
   
 
    vector<int> resp;
 
    while(!pq.empty()){
        int cur = pq.top();
 
        pq.pop();
        if(check[cur] == 2)
            continue;
 
        if(deg[cur]>=2){//check comp
            bool failed = 0;
 
            for(int i = 1; i < 4; i+=2){
                int k = i+1;
                int sum = 0;
                while(k != i+4){
                    int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
                    sum+=adj[cur][k] < n && check[adj[cur][k]] < 2;
                    k++;
                }
 
                if(sum < deg[cur] && sum > 0 && find(adj[cur][i],find) == find(adj[cur][i+4],find)){
                    failed = 1;
                    break;
                }
            }
 
            for(int i = 1; i < 8; i+=2){ 
                if(find(adj[cur][i],find) == find(adj[cur][(i+2)%8],find) && adj[cur][(i+1)%8] < n && check[adj[cur][(i+1)%8]] < 2){
                    failed = 1;
                    break;
                }
            }
            if(failed){
                check[cur] = 0;
                continue;
            }
 
        }
 
        check[cur] = 2;
        resp.push_back(cur);
        //cout << "push " << cur << '\n';
        dfs(cur,dfs);
        for(int i = 0; i < 8; i++){
            const int curval = adj[cur][i];
            if(curval < n){
                deg[curval]--;
                if(!check[curval] && reached[curval])
                    pq.push(curval), check[curval] = 1;
            }
        }
        for(int i = 1; i < 8; i+=2){
            const int curval = adj[cur][i];
            if(curval >= n || check[curval] == 2){
                onion(cur,curval);
            }
        }
    }
    reverse(all(resp));
 
    if(resp.size() == n){
        cout << "YES\n";
        for(int i : resp)
            cout << i + 1 << '\n';
    } else cout << "NO\n";
 
 
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:164:25: warning: unused variable 'xi' [-Wunused-variable]
  164 |                     int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
      |                         ^~
skyscrapers.cpp:164:48: warning: unused variable 'yi' [-Wunused-variable]
  164 |                     int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
      |                                                ^~
skyscrapers.cpp:209:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  209 |     if(resp.size() == n){
      |        ~~~~~~~~~~~~^~~~
skyscrapers.cpp:33:9: warning: unused variable 'dx' [-Wunused-variable]
   33 |     int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
      |         ^~
skyscrapers.cpp:33:25: warning: unused variable 'dy' [-Wunused-variable]
   33 |     int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
      |                         ^~

• 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