oj.uz

Submission #1108474

# Submission time Handle Problem Language Result Execution time Memory
1108474 2024-11-04T08:16:36 Z crafticat Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 801 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using pi = pair<int,int>;

#define F0R(i,n) for (int i = 0; i < n;i++)
#define FOR(i, j, n) for(int i = j; i < n;i++)
#define ckmin(x,y) x = min(x,y)
#define f first
#define s second

vi dx = {0,1,0,-1};
vi dy = {1,0,-1,0};

V<V<V<pi>>> grid;
V<vi> exists;
V<vb> visited;

void dfs(int x, int y) {
    visited[x][y] = true;
    if (exists[x][y] > 0) return;

    for (auto [cX, cY] : grid[x][y]) {
        if (visited[cX][cY]) continue;
        dfs(cX,cY);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, t; cin >> n >> t;
    V<pi> points(n);

    int startX = 1e9, startY = 1e9;

    F0R(i, n) {
        int x, y; cin >> x >> y;
        points[i] = {x,y};
        ckmin(startX, x);
        ckmin(startY, y);
    }
    startX-=3;
    startY-=3;

    grid.resize(n + 10, V<V<pi>>(n + 10));
    exists.resize(n + 10, vi(n + 10));
    visited.resize(n + 10, vb(n + 10));

    F0R(i, n) {
        points[i].f -= startX;
        points[i].s -= startY;

        if (points[i].f >= n + 7 || points[i].s >= n + 7) {
            cout << "NO\n";
            return 0;
        }

        exists[points[i].f][points[i].s] = i + 1;
    }

    FOR(i, 1, grid.size() - 1) {
        FOR(j, 1, grid[i].size() - 1) {
            F0R(k, 4) {
                grid[i][j].push_back({i + dx[k], j + dy[k]});
            }
        }
    }

    dfs(1,1);
    F0R(i, n) {
        if (!visited[points[i].f][points[i].s]) {
            cout << "NO\n";
            return 0;
        }
    }

    priority_queue<int, vi, greater<>> pq;
    vb vis(n + 1);
    pq.emplace(1);
    vi ans;

    while (!pq.empty()) {
        auto i = pq.top(); pq.pop();
        if (vis[i]) continue;
        vis[i] = true;
        ans.push_back(i);

        for (int delX = -1; delX < 2; delX++) {
            for (int delY = -1; delY < 2; ++delY) {
                int id = exists[points[i - 1].f + delX][points[i - 1].s + delY];
                if (id == 0) continue;
                if (vis[id]) continue;
                pq.emplace(id);
            }
        }
    }

    if (ans.size() != n) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    for (auto x : ans)
        cout << x << "\n";

    return 0;
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, std::allocator<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > > >, std::allocator<std::vector<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, std::allocator<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > > > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int i = j; i < n;i++)
......
   67 |     FOR(i, 1, grid.size() - 1) {
      |         ~~~~~~~~~~~~~~~~~~~~~          
skyscrapers.cpp:67:5: note: in expansion of macro 'FOR'
   67 |     FOR(i, 1, grid.size() - 1) {
      |     ^~~
skyscrapers.cpp:12:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, std::allocator<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, j, n) for(int i = j; i < n;i++)
......
   68 |         FOR(j, 1, grid[i].size() - 1) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~   
skyscrapers.cpp:68:9: note: in expansion of macro 'FOR'
   68 |         FOR(j, 1, grid[i].size() - 1) {
      |         ^~~
skyscrapers.cpp:104:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     if (ans.size() != n) {
      |         ~~~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB ans=YES N=1
2 Correct 1 ms 336 KB ans=YES N=4
3 Correct 1 ms 336 KB ans=NO N=4
4 Correct 1 ms 336 KB ans=YES N=5
5 Incorrect 1 ms 348 KB Contestant did not find solution
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB ans=YES N=1
2 Correct 1 ms 336 KB ans=YES N=4
3 Correct 1 ms 336 KB ans=NO N=4
4 Correct 1 ms 336 KB ans=YES N=5
5 Incorrect 1 ms 348 KB Contestant did not find solution
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB ans=YES N=1
2 Correct 1 ms 336 KB ans=YES N=4
3 Correct 1 ms 336 KB ans=NO N=4
4 Correct 1 ms 336 KB ans=YES N=5
5 Incorrect 1 ms 348 KB Contestant did not find solution
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 104520 KB ans=NO N=1934
2 Correct 636 ms 411208 KB ans=NO N=1965
3 Incorrect 577 ms 355892 KB Contestant did not find solution
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB ans=YES N=1
2 Correct 1 ms 336 KB ans=YES N=4
3 Correct 1 ms 336 KB ans=NO N=4
4 Correct 1 ms 336 KB ans=YES N=5
5 Incorrect 1 ms 348 KB Contestant did not find solution
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 801 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 104520 KB ans=NO N=1934
2 Correct 636 ms 411208 KB ans=NO N=1965
3 Incorrect 577 ms 355892 KB Contestant did not find solution
4 Halted 0 ms 0 KB -