oj.uz

Submission #982889

# Submission time Handle Problem Language Result Execution time Memory
982889 2024-05-15T00:37:13 Z duckindog Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 156 ms 27216 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4600 KB ans=YES N=1
2 Correct 1 ms 4444 KB ans=YES N=4
3 Correct 1 ms 4444 KB ans=NO N=4
4 Correct 1 ms 4500 KB ans=YES N=5
5 Correct 1 ms 4608 KB ans=YES N=9
6 Correct 1 ms 4444 KB ans=YES N=5
7 Correct 2 ms 4444 KB ans=NO N=9
8 Correct 1 ms 4444 KB ans=NO N=10
9 Correct 1 ms 4444 KB ans=YES N=10
10 Correct 1 ms 4444 KB ans=YES N=10
11 Correct 1 ms 4600 KB ans=YES N=10
12 Correct 1 ms 4440 KB ans=YES N=9
13 Correct 1 ms 4444 KB ans=YES N=9
14 Correct 1 ms 4444 KB ans=YES N=8
15 Correct 1 ms 4444 KB ans=YES N=8
16 Correct 1 ms 4444 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4600 KB ans=YES N=1
2 Correct 1 ms 4444 KB ans=YES N=4
3 Correct 1 ms 4444 KB ans=NO N=4
4 Correct 1 ms 4500 KB ans=YES N=5
5 Correct 1 ms 4608 KB ans=YES N=9
6 Correct 1 ms 4444 KB ans=YES N=5
7 Correct 2 ms 4444 KB ans=NO N=9
8 Correct 1 ms 4444 KB ans=NO N=10
9 Correct 1 ms 4444 KB ans=YES N=10
10 Correct 1 ms 4444 KB ans=YES N=10
11 Correct 1 ms 4600 KB ans=YES N=10
12 Correct 1 ms 4440 KB ans=YES N=9
13 Correct 1 ms 4444 KB ans=YES N=9
14 Correct 1 ms 4444 KB ans=YES N=8
15 Correct 1 ms 4444 KB ans=YES N=8
16 Correct 1 ms 4444 KB ans=NO N=2
17 Correct 2 ms 4696 KB ans=YES N=17
18 Correct 1 ms 4444 KB ans=YES N=25
19 Incorrect 2 ms 4440 KB Added cell 99 (4,1) not reachable from infinity
20 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4600 KB ans=YES N=1
2 Correct 1 ms 4444 KB ans=YES N=4
3 Correct 1 ms 4444 KB ans=NO N=4
4 Correct 1 ms 4500 KB ans=YES N=5
5 Correct 1 ms 4608 KB ans=YES N=9
6 Correct 1 ms 4444 KB ans=YES N=5
7 Correct 2 ms 4444 KB ans=NO N=9
8 Correct 1 ms 4444 KB ans=NO N=10
9 Correct 1 ms 4444 KB ans=YES N=10
10 Correct 1 ms 4444 KB ans=YES N=10
11 Correct 1 ms 4600 KB ans=YES N=10
12 Correct 1 ms 4440 KB ans=YES N=9
13 Correct 1 ms 4444 KB ans=YES N=9
14 Correct 1 ms 4444 KB ans=YES N=8
15 Correct 1 ms 4444 KB ans=YES N=8
16 Correct 1 ms 4444 KB ans=NO N=2
17 Correct 2 ms 4696 KB ans=YES N=17
18 Correct 1 ms 4444 KB ans=YES N=25
19 Incorrect 2 ms 4440 KB Added cell 99 (4,1) not reachable from infinity
20 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5896 KB ans=NO N=1934
2 Correct 3 ms 4952 KB ans=NO N=1965
3 Incorrect 3 ms 4792 KB Added cell 1824 (355,227) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4600 KB ans=YES N=1
2 Correct 1 ms 4444 KB ans=YES N=4
3 Correct 1 ms 4444 KB ans=NO N=4
4 Correct 1 ms 4500 KB ans=YES N=5
5 Correct 1 ms 4608 KB ans=YES N=9
6 Correct 1 ms 4444 KB ans=YES N=5
7 Correct 2 ms 4444 KB ans=NO N=9
8 Correct 1 ms 4444 KB ans=NO N=10
9 Correct 1 ms 4444 KB ans=YES N=10
10 Correct 1 ms 4444 KB ans=YES N=10
11 Correct 1 ms 4600 KB ans=YES N=10
12 Correct 1 ms 4440 KB ans=YES N=9
13 Correct 1 ms 4444 KB ans=YES N=9
14 Correct 1 ms 4444 KB ans=YES N=8
15 Correct 1 ms 4444 KB ans=YES N=8
16 Correct 1 ms 4444 KB ans=NO N=2
17 Correct 2 ms 4696 KB ans=YES N=17
18 Correct 1 ms 4444 KB ans=YES N=25
19 Incorrect 2 ms 4440 KB Added cell 99 (4,1) not reachable from infinity
20 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 13772 KB ans=NO N=66151
2 Correct 156 ms 27216 KB ans=NO N=64333
3 Incorrect 114 ms 13060 KB Added cell 69316 (-46,-72) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5896 KB ans=NO N=1934
2 Correct 3 ms 4952 KB ans=NO N=1965
3 Incorrect 3 ms 4792 KB Added cell 1824 (355,227) not reachable from infinity
4 Halted 0 ms 0 KB -