oj.uz

Submission #934737

# Submission time Handle Problem Language Result Execution time Memory
934737 2024-02-27T22:15:42 Z Alebn Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 180 ms 21664 KB 
#include <bits/stdc++.h>

using namespace std;

struct Cord {
    int x, y;
    Cord(){}
    Cord(int xi, int yi):x(xi),y(yi){}
};
bool operator<(const Cord a, const Cord b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
vector<Cord> dir = {
    Cord(-1, -1),
    Cord(-1, 0),
    Cord(-1, 1),
    Cord(0, 1), 
    Cord(1, 1),
    Cord(1, 0),
    Cord(1, -1),
    Cord(0, -1),
};

map<Cord, int> graph, visited, indx;
vector<int> res;

void dfs(Cord i) {
    visited[i] = 1;
    res.push_back(indx[i]);
    for(auto j : dir) {
        Cord next(i.x + j.x, i.y + j.y);
        if(graph[next] && !visited[next]) dfs(next);
    }
}

int main() {
    int n, t;
    cin >> n >> t;
    vector<Cord> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        graph[a[i]] = 1;
        indx[a[i]] = i;
    }
    //
    Cord start = a[0];
    for(auto i : a) {
        if(i.x < start.x || i.y < start.y) start = i;
    }
    //
    dfs(start);
    bool ok = true;
    for(int i = 0; i < n; i++) {
        if(!visited[a[i]]) {
            ok = false;
            break;
        }
    }
    if(ok) {
        cout << "YES\n";
        for(auto i : res) cout << i + 1 << "\n";
        cout << "\n";
    }
    else cout << "NO\n";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ans=YES N=1
2 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 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 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 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 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 576 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 3 ms 860 KB Added cell 1817 (374,214) not reachable from infinity
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 Correct 1 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Incorrect 0 ms 348 KB Added cell 5 (0,0) not reachable from infinity
7 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 21664 KB ans=NO N=66151
2 Correct 49 ms 9296 KB ans=NO N=64333
3 Incorrect 180 ms 21608 KB Added cell 69312 (147,-46) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 576 KB ans=NO N=1934
2 Correct 1 ms 604 KB ans=NO N=1965
3 Incorrect 3 ms 860 KB Added cell 1817 (374,214) not reachable from infinity
4 Halted 0 ms 0 KB -