Submission #934737

#	Time	Username	Problem	Language	Result	Execution time	Memory
934737		Alebn	Building Skyscrapers (CEOI19_skyscrapers)	C++14	0 / 100	180 ms	21664 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

struct Cord {
    int x, y;
    Cord(){}
    Cord(int xi, int yi):x(xi),y(yi){}
};
bool operator<(const Cord a, const Cord b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
vector<Cord> dir = {
    Cord(-1, -1),
    Cord(-1, 0),
    Cord(-1, 1),
    Cord(0, 1), 
    Cord(1, 1),
    Cord(1, 0),
    Cord(1, -1),
    Cord(0, -1),
};

map<Cord, int> graph, visited, indx;
vector<int> res;

void dfs(Cord i) {
    visited[i] = 1;
    res.push_back(indx[i]);
    for(auto j : dir) {
        Cord next(i.x + j.x, i.y + j.y);
        if(graph[next] && !visited[next]) dfs(next);
    }
}

int main() {
    int n, t;
    cin >> n >> t;
    vector<Cord> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        graph[a[i]] = 1;
        indx[a[i]] = i;
    }
    //
    Cord start = a[0];
    for(auto i : a) {
        if(i.x < start.x || i.y < start.y) start = i;
    }
    //
    dfs(start);
    bool ok = true;
    for(int i = 0; i < n; i++) {
        if(!visited[a[i]]) {
            ok = false;
            break;
        }
    }
    if(ok) {
        cout << "YES\n";
        for(auto i : res) cout << i + 1 << "\n";
        cout << "\n";
    }
    else cout << "NO\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