oj.uz

Submission #943953

# Submission time Handle Problem Language Result Execution time Memory
943953 2024-03-12T05:26:18 Z vjudge1 Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 155 ms 13004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}

const vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
const vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, t; cin >> n >> t;
  int x[n], y[n];
  map<int, map<int, bool>> vis;
  map<int, map<int, int>> used;
  int Min = -1;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
    used[x[i]][y[i]] = i + 1;
    if (Min == -1 || x[Min] + y[Min] > x[i] + y[i]) {
      Min = i;
    }
  }
  vector<int> res;
  priority_queue<array<int, 2>, 
    vector<array<int, 2>>,
    greater<array<int, 2>>> q;
  q.push({x[Min] + y[Min], Min});
  vis[x[Min]][y[Min]] = true;
  while (!q.empty()) {
    int i = q.top()[1];
    res.push_back(i + 1);
    q.pop();
    for (int j = 0; j < 8; ++j) {
      int to_x = x[i] + dx[j], to_y = y[i] + dy[j];
      if (used[to_x][to_y]) {
        if (!vis[to_x][to_y]) {
          vis[to_x][to_y] = true;
          q.push({to_x + to_y, used[to_x][to_y] - 1});
        }
      }
    }
  }
  if (size(res) < n) {
    cout << "NO";
    return 0;
  }
  reverse(all(res));
  cout << "YES\n";
  for (auto i : res) cout << i << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Incorrect 0 ms 348 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 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Incorrect 0 ms 348 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 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Incorrect 0 ms 348 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 1 ms 600 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 3 ms 604 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 0 ms 348 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Incorrect 0 ms 348 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 13004 KB ans=NO N=66151
2 Correct 24 ms 5456 KB ans=NO N=64333
3 Incorrect 155 ms 11208 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 1 ms 600 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 3 ms 604 KB Full cells must be connected
4 Halted 0 ms 0 KB -