oj.uz

Submission #850527

# Submission time Handle Problem Language Result Execution time Memory
850527 2023-09-16T19:37:17 Z faruk Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 3500 ms 244472 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;

vector<pii> moves = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

map<pii, int> ind;
set<pii> there;
set<pii> visited;
void dfs(pii a) {
    visited.insert(a);
    for (pii b : moves){
        pii neww(a.first + b.first, a.second + b.second);
        if (!visited.count(neww) and there.count(neww))
            dfs(neww);
    }
}

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

    int n;
    int t;
    cin >> n >> t;
    for (int i = 0; i < n; i++) {
        pii a;
        cin >> a.first >> a.second;
        there.insert(a);
        ind[a] = i + 1;
    }
    dfs(*there.begin());
    if (visited.size() != n) {
        cout <<"NO\n";
        return 0;
    }

    cout << "YES\n";
    queue<pii> q;
    q.push(*there.begin());
    visited.clear();
    while (!q.empty()) {
        pii a = q.front(); q.pop();
        cout << ind[a] << "\n";
        visited.insert(a);
        for (pii b : moves) {
            pii neww(a.first + b.first, a.second + b.second);
            if (!visited.count(neww) and there.count(neww))
                q.push(neww);
        }
    }
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:39:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     if (visited.size() != n) {
      |         ~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ans=YES N=1
2 Incorrect 0 ms 344 KB Extra information in the output file
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ans=YES N=1
2 Incorrect 0 ms 344 KB Extra information in the output file
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ans=YES N=1
2 Incorrect 0 ms 344 KB Extra information in the output file
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB ans=NO N=1934
2 Correct 1 ms 600 KB ans=NO N=1965
3 Execution timed out 3538 ms 244472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ans=YES N=1
2 Incorrect 0 ms 344 KB Extra information in the output file
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15656 KB ans=NO N=66151
2 Correct 49 ms 8124 KB ans=NO N=64333
3 Execution timed out 3534 ms 236072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB ans=NO N=1934
2 Correct 1 ms 600 KB ans=NO N=1965
3 Execution timed out 3538 ms 244472 KB Time limit exceeded
4 Halted 0 ms 0 KB -