oj.uz

Submission #519133

# Submission time Handle Problem Language Result Execution time Memory
519133 2022-01-25T17:53:46 Z fallingstar Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 2 ms 3824 KB 
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

map<pair<int, int>, int> mp;

const int N = 1.5e5 + 2;

vector<int> g[N];
int deg[N];
vector<int> ord;

void dfs(int u)
{
    deg[u] = 0;
    ord.push_back(u);
    int cand = -1;
    for (int v : g[u])
        if (deg[v] > 0 && (cand == -1 || deg[v] < deg[cand]))
            cand = v;
    if (cand != -1) {
        for (int v : g[u])
            if (deg[v] > 0) --deg[v];
        dfs(cand);
    }
}

int main()
{
    int n; cin >> n;
    int subtask; cin >> subtask;
    if (subtask == 2) return 1;
    for (int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;

        for (int dir = 0; dir < 8; ++dir) {
            int u = x + dx[dir], v = y + dy[dir];
            if (auto it = mp.find({u, v}); it != mp.end()) {
                int j = it->second;
                g[i].push_back(j);
                g[j].push_back(i);
                ++deg[i], ++deg[j];
            }
        }

        mp[{x, y}] = i;
    }

    int st = 0;
    for (int i = 1; i < n; ++i)
        if (g[i].size() < g[st].size()) st = i;

    dfs(st);
    for (int i = 0; i < n; ++i)
        if (deg[i] > 0) {
            cout << "NO";
            return 0;
        }
    reverse(ord.begin(), ord.end());
    cout << "YES\n";
    for (int u : ord) cout << u + 1 << '\n';
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3824 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Incorrect 2 ms 3788 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3824 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Incorrect 2 ms 3788 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3824 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Incorrect 2 ms 3788 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 3788 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3824 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Incorrect 2 ms 3788 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 3816 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 3788 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -