oj.uz

Submission #476886

# Submission time Handle Problem Language Result Execution time Memory
476886 2021-09-28T23:27:51 Z Ozy Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 1666 ms 1048580 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);
    for(auto h : hijos[pos]) {
        if (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 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3836 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3836 KB Each cell must be removed exactly once
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3836 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3836 KB Each cell must be removed exactly once
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3836 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3836 KB Each cell must be removed exactly once
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3916 KB ans=NO N=1934
2 Correct 5 ms 4112 KB ans=NO N=1965
3 Runtime error 1409 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 2 ms 3788 KB ans=YES N=4
3 Correct 3 ms 3836 KB ans=NO N=4
4 Correct 2 ms 3788 KB ans=YES N=5
5 Incorrect 2 ms 3836 KB Each cell must be removed exactly once
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 14316 KB ans=NO N=66151
2 Correct 139 ms 9208 KB ans=NO N=64333
3 Runtime error 1666 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3916 KB ans=NO N=1934
2 Correct 5 ms 4112 KB ans=NO N=1965
3 Runtime error 1409 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -