Submission #982889

#	Time	Username	Problem	Language	Result	Execution time	Memory
982889		duckindog	Building Skyscrapers (CEOI19_skyscrapers)	C++17	8 / 100	156 ms	27216 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

const int N = 150'000 + 10,
          dx[8] = {0, 1, 0, -1, 1, 1, -1, -1},
          dy[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int n, t;
int r[N], c[N];
map<int, map<int, int>> id;
vector<int> ad[N];
bool mk[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> t;
  for (int i = 1; i <= n; ++i) { 
    cin >> r[i] >> c[i];
    id[r[i]][c[i]] = i;
  }

  for (int i = 1; i <= n; ++i) { 
    for (int j = 0; j < 8; ++j) { 
      int nR = r[i] + dx[j], nC = c[i] + dy[j];
      int nxt = id[nR][nC];
      if (!nxt) continue;
      ad[i].push_back(nxt);
    }
  }

  priority_queue<int> q;
  vector<int> answer;
  q.push(1); mk[1] = true;
  while (q.size()) { 
    int u = q.top(); q.pop();
    answer.push_back(u);

    for (const auto& v : ad[u]) { 
      if (mk[v]) continue;
      mk[v] = true;
      q.push(v);
    }
  }
  
  if (answer.size() != n) { cout << "NO\n"; return 0; }
  cout << "YES\n";
  for (const auto& x : answer) cout << x << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 8 / 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