제출 #779293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779293		definitelynotmee	Building Skyscrapers (CEOI19_skyscrapers)	C++17	100 / 100	3111 ms	156176 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;
 
    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});
            }
        }
    }
    pai = vector<int>(t);
    iota(all(pai),0);
 
    for(int i = n; i < t; i++){
        for(int j = 0; j < 4; j++){
            int xi = v[i].ff+dx[j], yi = v[i].ss+dy[j];
            if(mp.count({xi,yi}) && mp[{xi,yi}] >= n){
                onion(i,mp[{xi,yi}]);
            }
        }
    }
 
 
 
 
    vector<int> check(n);
 
    priority_queue<int> pq;
 
    set<pii> passed;
    vector<int> reached(n);
 
    auto dfs =[&](int x, int y, auto dfs) -> void {
        passed.insert({x,y});
        for(int i = 0; i < 4; i++){
            int xi = x+dx[i], yi = y+dy[i];
            if(!passed.count({xi,yi}) && mp.count({xi,yi})){
                int curval = mp[{xi,yi}];
 
                if(curval >= n){
                    dfs(xi,yi,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(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 leftx = v[cur].ff+dx2[i], lefty = v[cur].ss+dy2[i];
                int rightx = v[cur].ff+dx2[i+4], righty = v[cur].ss+dy2[i+4];
                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+=mp[{xi,yi}] < n && check[mp[{xi,yi}]] < 2;
                    k++;
                }
 
                if(sum < deg[cur] && sum > 0 && find(mp[{leftx,lefty}],find) == find(mp[{rightx,righty}],find)){
                    failed = 1;
                    break;
                }
            }
 
            for(int i = 1; i < 8; i+=2){
                int xi = v[cur].ff+dx2[i], yi = v[cur].ss+dy2[i];
                int nxi = v[cur].ff+dx2[(i+1)%8], nyi = v[cur].ss+dy2[(i+1)%8];
                int nnxi = v[cur].ff+dx2[(i+2)%8], nnyi = v[cur].ss+dy2[(i+2)%8];
 
                if(find(mp[{xi,yi}],find) == find(mp[{nnxi,nnyi}],find) && mp[{nxi,nyi}] < n && check[mp[{nxi,nyi}]] < 2){
                    failed = 1;
                    break;
                }
            }
            if(failed){
                check[cur] = 0;
                continue;
            }
 
        }
        check[cur] = 2;
        resp.push_back(cur);
        //cout << "push " << cur << '\n';
        dfs(v[cur].ff,v[cur].ss,dfs);
        for(int i = 0; i < 8; i++){
            int xi = v[cur].ff+dx2[i], yi = v[cur].ss+dy2[i];
            if(mp[{xi,yi}] < n){
                deg[mp[{xi,yi}]]--;
                if(!check[mp[{xi,yi}]] && reached[mp[{xi,yi}]])
                    pq.push(mp[{xi,yi}]), check[mp[{xi,yi}]] = 1;
            }
        }
        for(int i = 0; i < 4; i++){
            int xi = v[cur].ff+dx[i], yi = v[cur].ss+dy[i];
            if(mp[{xi,yi}] >= n || check[mp[{xi,yi}]] == 2){
                onion(cur,mp[{xi,yi}]);
            }
        }
    }
    reverse(all(resp));
 
    if(resp.size() == n){
        cout << "YES\n";
        for(int i : resp)
            cout << i + 1 << '\n';
    } else cout << "NO\n";
 
 
}

컴파일 시 표준 에러 (stderr) 메시지

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:199:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  199 |     if(resp.size() == n){
      |        ~~~~~~~~~~~~^~~~

• 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