oj.uz

Submission #518683

# Submission time Handle Problem Language Result Execution time Memory
518683 2022-01-24T12:18:53 Z Monarchuwu Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 3500 ms 273252 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 2e5 + 8;
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
int n, t;
struct Point {
    int x, y, id;
    Point() {}
    bool operator < (const Point &o) const {
        return y < o.y;
    }
} p[N];
int b[N], mx, my;
void compress() {
    for (int i = 1; i <= n; ++i) {
        b[++mx] = p[i].x - 1;
        b[++mx] = p[i].x;
        b[++mx] = p[i].x + 1;
    }
    sort(b + 1, b + mx + 1);
    mx = unique(b + 1, b + mx + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        p[i].x = lower_bound(b + 1, b + mx + 1, p[i].x) - b;

    for (int i = 1; i <= n; ++i) {
        b[++my] = p[i].y - 1;
        b[++my] = p[i].y;
        b[++my] = p[i].y + 1;
    }
    sort(b + 1, b + my + 1);
    my = unique(b + 1, b + my + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        p[i].y = lower_bound(b + 1, b + my + 1, p[i].y) - b;
}

vector<int> g[N];
bool vis[666][666], abc[666][666];
bool avail(int x, int y) {
    for (int i = 0; i < 606; ++i)
        for (int j = 0; j < 606; ++j)
            abc[i][j] = vis[i][j];

    queue<pii> q;
    q.emplace(x, y);
    abc[x][y] = true;
    while (!q.empty()) {
        x = q.front().ff, y = q.front().ss; q.pop();
        if (x == 0 || x == 601 || y == 0 || y == 601) return true;

        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (!abc[xx][yy]) {
                abc[xx][yy] = true;
                q.emplace(xx, yy);
            }
        }
    }
    return false;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].x >> p[i].y, p[i].id = i;
    sort(p + 1, p + n + 1);
    compress();

    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            if (abs(p[i].x - p[i].x) <= 1 && abs(p[i].y - p[j].y) <= 1) {
                g[p[i].id].push_back(p[j].id);
                g[p[j].id].push_back(p[i].id);
            }
        }

    vector<int> ans(1, p[1].id);
    vis[p[1].x][p[1].y] = true;
    queue<int> q;
    q.push(p[1].id);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (!vis[p[v].x][p[v].y]) {
            if (avail(p[v].x, p[v].y))
                ans.push_back(p[v].id);
            else ans.insert(ans.begin(), p[v].id);

            vis[p[v].x][p[v].y] = true;
            q.push(p[v].id);
        }
    }

    if (ans.size() != n) cout << "NO\n";
    else {
        cout << "YES\n";
        for (int x : ans) cout << x << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB ans=YES N=1
2 Correct 3 ms 5324 KB ans=YES N=4
3 Correct 4 ms 5328 KB ans=NO N=4
4 Incorrect 3 ms 5412 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB ans=YES N=1
2 Correct 3 ms 5324 KB ans=YES N=4
3 Correct 4 ms 5328 KB ans=NO N=4
4 Incorrect 3 ms 5412 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB ans=YES N=1
2 Correct 3 ms 5324 KB ans=YES N=4
3 Correct 4 ms 5328 KB ans=NO N=4
4 Incorrect 3 ms 5412 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5020 KB ans=NO N=1934
2 Incorrect 157 ms 6528 KB Full cells must be connected
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB ans=YES N=1
2 Correct 3 ms 5324 KB ans=YES N=4
3 Correct 4 ms 5328 KB ans=NO N=4
4 Incorrect 3 ms 5412 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3535 ms 273252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5020 KB ans=NO N=1934
2 Incorrect 157 ms 6528 KB Full cells must be connected
3 Halted 0 ms 0 KB -