oj.uz

Submission #346391

# Submission time Handle Problem Language Result Execution time Memory
346391 2021-01-09T13:46:25 Z doowey Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 193 ms 15328 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);

int dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,-1},{0,+1},{1,-1},{1,0},{1,+1}};

map<pii,int> indx;
map<pii,bool> vis;
int cnt;

void dfs(pii go){
    pii nx;
    vis[go]=true;
    cnt ++ ;
    for(int d = 0 ; d < 8 ; d ++ ){
        nx = mp(go.fi + dir[d][0], go.se + dir[d][1]);
        if(indx.count(nx)){
            if(!vis.count(nx)){
                dfs(nx);
            }
        }
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int typ;
    cin >> typ;
    pii cc;
    vector<pii> ass;
    for(int i = 1; i <= n; i ++ ){
        cin >> cc.fi >> cc.se;
        indx[cc]=i;
        ass.push_back(cc);
    }
    sort(ass.begin(), ass.end());
    dfs(ass[0]);
    if(cnt != n){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(int i = n - 1; i >= 0 ; i -- ){
        cout << indx[ass[i]] << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB ans=YES N=1
2 Correct 0 ms 364 KB ans=YES N=4
3 Correct 0 ms 364 KB ans=NO N=4
4 Incorrect 1 ms 364 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 0 ms 364 KB ans=YES N=1
2 Correct 0 ms 364 KB ans=YES N=4
3 Correct 0 ms 364 KB ans=NO N=4
4 Incorrect 1 ms 364 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 0 ms 364 KB ans=YES N=1
2 Correct 0 ms 364 KB ans=YES N=4
3 Correct 0 ms 364 KB ans=NO N=4
4 Incorrect 1 ms 364 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 2 ms 492 KB ans=NO N=1934
2 Correct 2 ms 492 KB ans=NO N=1965
3 Incorrect 4 ms 748 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 0 ms 364 KB ans=YES N=1
2 Correct 0 ms 364 KB ans=YES N=4
3 Correct 0 ms 364 KB ans=NO N=4
4 Incorrect 1 ms 364 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 156 ms 13664 KB ans=NO N=66151
2 Correct 48 ms 4836 KB ans=NO N=64333
3 Incorrect 193 ms 15328 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 2 ms 492 KB ans=NO N=1934
2 Correct 2 ms 492 KB ans=NO N=1965
3 Incorrect 4 ms 748 KB Full cells must be connected
4 Halted 0 ms 0 KB -