oj.uz

Submission #347270

# Submission time Handle Problem Language Result Execution time Memory
347270 2021-01-12T13:13:29 Z doowey Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 1709 ms 119892 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int d4[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};
int d8[8][2] = {{-1,-1},{0,-1},{+1,-1},{+1,0},{+1,+1},{0,+1},{-1,+1},{-1,0}};

const int N = 150101;
const int M = N * 9;
set<int> Q[M];
map<pii,int> idx;
map<pii,int> emp;
map<pii,int> out;
int ii[N], jj[N];
pii vv[M];
int par[M];
int id;

bool active[M];

int fin(int x){
    if(x==par[x]) return x;
    return par[x]=fin(par[x]);
}

void unite(int p, int q){
    // an element can be added at most 8? times therefore it is optimal
    p=fin(p);
    q=fin(q);
    if(p==q) return;
    if(Q[p].size() > Q[q].size()) swap(p,q);
    par[p]=q;
    for(auto x : Q[p]){
        Q[q].insert(x);
    }
    Q[p].clear();
}

bool has[N];

void check(int id){
    has[id]=true;
    pii go;
    for(int t = 0 ; t < 8 ; t ++ ){
        go = mp(ii[id]+d8[t][0],jj[id]+d8[t][1]);
        if(idx.count(go)){
            if(!has[idx[go]]){
                check(idx[go]);
            }
        }
    }
}

bool can_kill(pii vv){
    vector<int> q;
    pii nx;
    int cnt = 0;
    for(int i = 0 ; i < 8 ; i ++ ){
        nx = mp(vv.fi + d8[i][0], vv.se + d8[i][1]);
        if(emp.count(nx)){
            q.push_back(fin(emp[nx]));
        }
        else{
            cnt ++ ;
            q.push_back(-1);
        }
    }
    if(cnt <= 1 || cnt >= 7) return true;
    int pv, qv;
    for(int d = 0; d < 8; d += 2){ // corners
        pv = (d + 8 - 1) % 8;
        qv = (d + 1) % 8;
        if(q[d] == -1 && q[pv] >= 0 && q[pv] == q[qv]){
            return false;
        }
    }
    // side cut
    if(q[1] == q[5] && q[1] >= 0 && min({q[0],q[6],q[7]}) == -1 && min({q[2],q[3],q[4]}) == -1){
        return false;
    }
    if(q[3] == q[6] && q[3] >= 0 && min({q[0],q[1],q[2]}) == -1 && min({q[4],q[5],q[6]}) == -1){
        return false;
    }
    return true;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int typ;
    cin >> typ;
    for(int i = 1; i <= n; i ++) {
        cin >> ii[i] >> jj[i];
        idx[mp(ii[i],jj[i])] = i;
        active[i]=true;
    }
    pii nx;
    pii low = mp((int)1e9+7,(int)1e9+7);
    for(int i = 1; i <= n; i ++ ){
        for(int q = 0; q < 8; q ++ ){
            nx = mp(ii[i] + d8[q][0], jj[i] + d8[q][1]);
            if(idx.count(nx)) continue;
            if(!emp.count(nx)){
                emp[nx]=id;
                vv[id]=nx;
                par[id]=id;
                id++;
            }
            Q[emp[nx]].insert(i);
            low = min(low, nx);
        }
    }
    for(int i = 0 ; i < id; i ++ ){
        for(int j = 0 ; j < 4; j ++) {
            nx = mp(vv[i].fi+d4[j][0], vv[i].se+d4[j][1]);
            if(emp.count(nx)){
                unite(i,emp[nx]);
            }
            else{
                if(idx.count(nx)){
                    Q[i].insert(idx[nx]);
                }
            }

        }
    }
    for(auto x : Q[fin(emp[low])]){
        out[mp(ii[x],jj[x])]=true;
    }
    check(1);
    for(int i = 1; i <= n; i ++ ){
        if(!has[i]){
            cout << "NO\n";
            return 0;
        }
    }
    vector<int> soln;
    int cid;
    int chk;
    int nah;
    for(int delet = 0 ; delet < n; delet ++ ){
        cid = fin(emp[low]);
        while(!Q[cid].empty()){
            auto it = Q[cid].end();
            -- it;
            chk = *it;
            Q[cid].erase(it);
            if(!active[chk]){
                continue;
            }
            if(can_kill(mp(ii[chk],jj[chk]))){
                active[chk]=false;
                soln.push_back(chk);
                idx[mp(ii[chk],jj[chk])]=0;
                emp[mp(ii[chk],jj[chk])]=id;
                par[id]=id;
                for(int d = 0; d < 4; d ++ ){
                    nx = mp(ii[chk]+d4[d][0],jj[chk]+d4[d][1]);
                    if(idx.count(nx) && idx[nx]>0){
                        out[nx]=true;
                        Q[id].insert(idx[nx]);
                    }
                }
                for(int d = 0 ;d < 4; d ++ ){
                    nx = mp(ii[chk]+d4[d][0],jj[chk]+d4[d][1]);
                    if(emp.count(nx)){
                        nah = emp[nx];
                        unite(id,nah);
                    }
                }
                for(int d = 0; d < 8 ; d ++ ){
                    nx = mp(ii[chk]+d8[d][0],jj[chk]+d8[d][1]);
                    if(idx[nx] > 0 && out.count(nx)){
                        Q[fin(id)].insert(idx[nx]);
                    }
                }
                id++;
                break;
            }
        }
    }
    reverse(soln.begin(), soln.end());
    cout << "YES\n";
    for(auto x : soln)
        cout << x << " ";
    cout << "\n";
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63852 KB ans=YES N=1
2 Correct 43 ms 63852 KB ans=YES N=4
3 Correct 42 ms 63852 KB ans=NO N=4
4 Correct 42 ms 63852 KB ans=YES N=5
5 Correct 42 ms 63852 KB ans=YES N=9
6 Correct 42 ms 63852 KB ans=YES N=5
7 Correct 42 ms 63852 KB ans=NO N=9
8 Correct 43 ms 63884 KB ans=NO N=10
9 Correct 43 ms 63852 KB ans=YES N=10
10 Incorrect 42 ms 63852 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63852 KB ans=YES N=1
2 Correct 43 ms 63852 KB ans=YES N=4
3 Correct 42 ms 63852 KB ans=NO N=4
4 Correct 42 ms 63852 KB ans=YES N=5
5 Correct 42 ms 63852 KB ans=YES N=9
6 Correct 42 ms 63852 KB ans=YES N=5
7 Correct 42 ms 63852 KB ans=NO N=9
8 Correct 43 ms 63884 KB ans=NO N=10
9 Correct 43 ms 63852 KB ans=YES N=10
10 Incorrect 42 ms 63852 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63852 KB ans=YES N=1
2 Correct 43 ms 63852 KB ans=YES N=4
3 Correct 42 ms 63852 KB ans=NO N=4
4 Correct 42 ms 63852 KB ans=YES N=5
5 Correct 42 ms 63852 KB ans=YES N=9
6 Correct 42 ms 63852 KB ans=YES N=5
7 Correct 42 ms 63852 KB ans=NO N=9
8 Correct 43 ms 63884 KB ans=NO N=10
9 Correct 43 ms 63852 KB ans=YES N=10
10 Incorrect 42 ms 63852 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 65772 KB ans=NO N=1934
2 Correct 56 ms 64732 KB ans=NO N=1965
3 Incorrect 60 ms 64448 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63852 KB ans=YES N=1
2 Correct 43 ms 63852 KB ans=YES N=4
3 Correct 42 ms 63852 KB ans=NO N=4
4 Correct 42 ms 63852 KB ans=YES N=5
5 Correct 42 ms 63852 KB ans=YES N=9
6 Correct 42 ms 63852 KB ans=YES N=5
7 Correct 42 ms 63852 KB ans=NO N=9
8 Correct 43 ms 63884 KB ans=NO N=10
9 Correct 43 ms 63852 KB ans=YES N=10
10 Incorrect 42 ms 63852 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 86508 KB ans=NO N=66151
2 Correct 1709 ms 119892 KB ans=NO N=64333
3 Incorrect 1196 ms 87012 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 65772 KB ans=NO N=1934
2 Correct 56 ms 64732 KB ans=NO N=1965
3 Incorrect 60 ms 64448 KB Full cells must be connected
4 Halted 0 ms 0 KB -