Submission #346398

#	Time	Username	Problem	Language	Result	Execution time	Memory
346398		doowey	Building Skyscrapers (CEOI19_skyscrapers)	C++14	0 / 100	280 ms	16612 KiB

skyscrapers

#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);

const int N = 151111;
int dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,-1},{0,+1},{1,-1},{1,0},{1,+1}};
map<pii,int> indx;
vector<int> T[N];
int dep[N];

void dfs(int u){
    for(auto x : T[u]){
        if(dep[x]==-1){
            dep[x]=dep[u]+1;
            dfs(x);
        }
    }
}

bool dead[N];
vector<int> soln;
void dfs1(int u){
    for(auto x : T[u]){
        if(dep[x] != dep[u] + 1 && dep[x] > dep[u]){
            if(!dead[x]){
                dead[x]=true;
                soln.push_back(x);
            }
        }
    }
    for(auto x : T[u]){
        if(dep[x] == dep[u] + 1){
            dfs1(x);
        }
    }
    if(!dead[u]){
        soln.push_back(u);
        dead[u]=true;
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int typ;
    cin >> typ;
    pii cc;
    pii nx;
    pii low = mp((int)1e9,(int)1e9);
    int pv;
    for(int i = 1; i <= n; i ++ ){
        cin >> cc.fi >> cc.se;
        indx[cc]=i;
        low = min(low, cc);
        for(int d = 0; d < 8 ; d ++ ){
            nx = mp(cc.fi+dir[d][0],cc.se+dir[d][1]);
            if(indx.count(nx)){
                pv = indx[nx];
                T[i].push_back(pv);
                T[pv].push_back(i);
            }
        }
        dep[i]=-1;
    }
    int root = indx[low];
    dep[root]=0;
    dfs(root);
    for(int i = 1; i <= n; i ++ ){
        if(dep[i] == -1){
            cout << "NO\n";
            return 0;
        }
    }
    dfs1(root);
    cout << "YES\n";
    reverse(soln.begin(),soln.end());
    for(auto q : soln){
        cout << q << "\n";
    }
    return 0;
}

• 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