oj.uz

Submission #346397

# Submission time Handle Problem Language Result Execution time Memory
346397 2021-01-09T14:18:44 Z doowey Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 278 ms 16740 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 151111;
int dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,-1},{0,+1},{1,-1},{1,0},{1,+1}};
map<pii,int> indx;
vector<int> T[N];
int dep[N];

void dfs(int u){
    for(auto x : T[u]){
        if(dep[x]==-1){
            dep[x]=dep[u]+1;
            dfs(x);
        }
    }
}

bool dead[N];
vector<int> soln;
void dfs1(int u){
    for(auto x : T[u]){
        if(dep[x] != dep[u] + 1 && dep[x] > dep[u]){
            if(!dead[x]){
                dead[x]=true;
                soln.push_back(x);
            }
        }
    }
    for(auto x : T[u]){
        if(dep[x] == dep[u] + 1){
            dfs1(x);
        }
    }
    if(!dead[u]){
        soln.push_back(u);
        dead[u]=true;
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int typ;
    cin >> typ;
    pii cc;
    pii nx;
    pii low = mp((int)1e9,(int)1e9);
    int pv;
    for(int i = 1; i <= n; i ++ ){
        cin >> cc.fi >> cc.se;
        indx[cc]=i;
        low = min(low, cc);
        for(int d = 0; d < 8 ; d ++ ){
            nx = mp(cc.fi+dir[d][0],cc.se+dir[d][1]);
            if(indx.count(nx)){
                pv = indx[nx];
                T[i].push_back(pv);
                T[pv].push_back(i);
            }
        }
        dep[i]=-1;
    }
    int root = indx[low];
    dep[root]=0;
    dfs(root);
    for(int i = 1; i <= n; i ++ ){
        if(dep[i] == -1){
            cout << "NO\n";
            return 0;
        }
    }
    dfs1(root);
    cout << "YES\n";
    for(auto q : soln){
        cout << q << "\n";
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3948 KB ans=YES N=1
2 Correct 3 ms 3948 KB ans=YES N=4
3 Correct 3 ms 3948 KB ans=NO N=4
4 Incorrect 3 ms 3948 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3948 KB ans=YES N=1
2 Correct 3 ms 3948 KB ans=YES N=4
3 Correct 3 ms 3948 KB ans=NO N=4
4 Incorrect 3 ms 3948 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3948 KB ans=YES N=1
2 Correct 3 ms 3948 KB ans=YES N=4
3 Correct 3 ms 3948 KB ans=NO N=4
4 Incorrect 3 ms 3948 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4076 KB ans=NO N=1934
2 Correct 5 ms 4076 KB ans=NO N=1965
3 Incorrect 7 ms 4204 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3948 KB ans=YES N=1
2 Correct 3 ms 3948 KB ans=YES N=4
3 Correct 3 ms 3948 KB ans=NO N=4
4 Incorrect 3 ms 3948 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 12268 KB ans=NO N=66151
2 Correct 116 ms 8960 KB ans=NO N=64333
3 Incorrect 278 ms 16740 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4076 KB ans=NO N=1934
2 Correct 5 ms 4076 KB ans=NO N=1965
3 Incorrect 7 ms 4204 KB Full cells must be connected
4 Halted 0 ms 0 KB -