oj.uz

Submission #476887

# Submission time Handle Problem Language Result Execution time Memory
476887 2021-09-28T23:29:22 Z Ozy Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 249 ms 16828 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 150000

lli n,t,a,b,act,k,num;
map<pair<lli,lli>, lli> mapa;
vector<lli> hijos[MAX+2];
lli dir[16] = {-1,0,1,0,-1,1,1,-1,0,1,0,-1,1,1,-1,-1};
lli visitados[MAX+2],dis[MAX+2];
queue<lli> cola;
vector<lli> res;

void dfs(lli pos) {

    res.push_back(pos);
    visitados[pos] = 2;

    for(auto h : hijos[pos]) {
        if (visitados[h] == 2 || dis[h] <= dis[pos]) continue;
        dfs(h);
    }

}

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

    cin >> n >> t;

    rep(i,1,n) {
        cin >> a >> b;

        mapa[{a,b}] = i;

        rep(o,0,7) {
            if (mapa.find({a+dir[o],b + dir[o+8]}) != mapa.end()) {
                k = mapa[{a+dir[o],b + dir[o+8]}];
                hijos[k].push_back(i);
                hijos[i].push_back(k);
            }
        }
    }
    //correcto

    cola.push(1);
    visitados[1] = 1;

    num = 0;
    while (!cola.empty()) {

        act = cola.front();
        cola.pop();
        num++;

        for(auto h : hijos[act]) {
            if (visitados[h] == 1) continue;
            visitados[h] = 1;
            dis[h] = dis[act] + 1;
            cola.push(h);
        }
    }

    if (num < n) {
        cout << "NO";
        return 0;
    }

    dfs(1);
    cout << "YES\n";
    for (auto r : res) cout << r << "\n";
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3788 KB Added cell 8 (1,1) not reachable from infinity
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3788 KB Added cell 8 (1,1) not reachable from infinity
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3788 KB Added cell 8 (1,1) not reachable from infinity
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3976 KB ans=NO N=1934
2 Correct 5 ms 4044 KB ans=NO N=1965
3 Incorrect 5 ms 4172 KB Added cell 1824 (356,209) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3788 KB Added cell 8 (1,1) not reachable from infinity
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 13852 KB ans=NO N=66151
2 Correct 119 ms 8656 KB ans=NO N=64333
3 Incorrect 249 ms 16828 KB Added cell 69316 (3,-133) 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 3976 KB ans=NO N=1934
2 Correct 5 ms 4044 KB ans=NO N=1965
3 Incorrect 5 ms 4172 KB Added cell 1824 (356,209) not reachable from infinity
4 Halted 0 ms 0 KB -