oj.uz

Submission #799502

# Submission time Handle Problem Language Result Execution time Memory
799502 2023-07-31T15:21:43 Z Ronin13 Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 1389 ms 51812 KB 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>

#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair

using namespace std;

const ll mod = 998244353;
const int nmax = 400001;

set <int> st[nmax];
int cnt[nmax];
set <int> good;
vector <vector <int> > vv(nmax);
bool out[nmax];
vector <int> p(nmax);
map <pii, int> m;
bool used[nmax];
int x[nmax], y[nmax];
vector <pii> d;
int n;

void dfs(int x, int y){
    used[m[mp(x, y)]] = true;
    for(int i = 0; i < d.size(); i++){
        int nx = x + d[i].f, ny = y + d[i].s;
        if(!m[mp(nx, ny)]) continue;
        if(used[m[mp(nx, ny)]]) continue;
        dfs(nx, ny);
    }
}

bool A[nmax], B[nmax];
int cur;

void make_set(int v){
    p[v] = v;
   // out[v] = true;
 //   sz[v] = 1;
}


int find_set(int v){
    return p[v] == v ? v : p[v] = find_set(p[v]);
}
void rem(int ind){
    good.erase(ind);
    B[ind] = false;
}

void add(int ind){
    if(cnt[ind] == st[ind].size()) B[ind] = true;
    if(A[ind] && B[ind])good.insert(ind);
}



void recount_regions(int ind){
    int lst = 0;
    cnt[ind] = 0;
    A[ind] = false;
    B[ind] = false;
    good.erase(ind);
    for(int i = 0; i < d.size(); i++){
        int nx = x[ind] + d[i].f, ny = y[ind] + d[i].s;
        if(m[mp(nx, ny)] > n) {
            lst = 1;
            A[ind] |= out[find_set(m[mp(nx, ny)])];
        }
        else{ if(lst == 1) cnt[ind]++; lst =0;}
    }
    if(!cnt[ind]) cnt[ind]++;
    if(cnt[ind] == st[ind].size()) B[ind] = true;
    if(A[ind] && B[ind]) good.insert(ind);
}

void union_sets(int a, int b){
    a = find_set(a);
     b= find_set(b);
     if(a == b) return;
     if(vv[a].size() < vv[b].size()) swap(a, b);
     p[b] = a;
    out[a] |= out[b];
    for(int i = 0; i < vv[b].size(); i++){
        int x = vv[b][i];
        rem(x);
        st[x].erase(b);
        st[x].insert(a);
        add(x);
        recount_regions(x);
        vv[a].pb(x);
    }
    
}

void make_empty(int ind){
    m[mp(x[ind], y[ind])] = cur++;
    make_set(cur - 1);
    for(int i = 0; i < d.size(); i++){
        int nx = d[i].f + x[ind], ny = d[i].s + y[ind];
        pii o = mp(nx, ny);
        if(m[o] > 0 && m[o] <= n) st[m[o]].insert(cur - 1), vv[cur - 1].pb(m[o]);
    }
    for(int i = 0; i < d.size(); i++){
        int nx = d[i].f + x[ind], ny = d[i].s + y[ind];
        if(d[i].f && d[i].s) continue;
        if(m[mp(nx, ny)] > n) union_sets(cur - 1, m[mp(nx, ny)]);
    }
    for(int i = 0; i < d.size(); i++){
        int nx = d[i].f + x[ind], ny = d[i].s + y[ind];
        pii o = mp(nx, ny);
        if(m[o] > 0 && m[o] <= n) recount_regions(m[o]);
    }
}

int main(){
    d.pb(mp(-1, -1)); d.pb(mp(-1, 0)); d.pb(mp(-1, 1)); 
    d.pb(mp(0, 1)); d.pb(mp(1, 1)); d.pb(mp(1, 0)); d.pb(mp(1, -1));
    d.pb(mp(0, -1)); d.pb(mp(-1, -1));
    cin >> n;
    int t; cin >> t;
    cur = n + 1;
    int mxx, mxy;
    mxy= mxx = -1e9 + 10;
    int mnx, mny;
    mnx = mny = 1e9 + 10;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        mxx = max(mxx, x[i]);
        mnx = min(mnx, x[i]);
        mxy = max(mxy, y[i]);
        mny = min(mny, y[i]);
        m[mp(x[i], y[i])] = i;
    }
    dfs(x[1], y[1]);
    for(int i = 1; i <= n; i++){
        if(!used[i]){
            cout << "NO\n";
            return 0;
        }
    }
    vector <pii> empt;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < d.size(); j++){
            int nx = x[i] + d[j].f, ny = y[i] + d[j].s;
            if(!m[mp(nx, ny)]){
                make_set(cur);
                if(nx < mnx || ny < mny || nx > mxx || ny > mxy)
                    out[cur] = true;
                empt.pb(mp(nx, ny));
                m[mp(nx, ny)] = cur++;
            }
           if(m[mp(nx, ny)] > n) st[i].insert(m[mp(nx, ny)]),
            vv[m[mp(nx, ny)]].pb(i);
        }
    }
    for(int i = 1; i <= n; i++)
        recount_regions(i);
    
    for(int i = 0; i <empt.size(); ++i){
        int x = empt[i].f, y = empt[i].s;
        for(int j = 0; j < d.size(); j++){
            int nx = x + d[j].f, ny = y + d[j].s;
            if(d[j].f != 0 && d[j].s != 0) continue;
            if(m[mp(nx, ny)] > n){
                union_sets(m[empt[i]], m[mp(nx, ny)]);
            }
        }
    }
    
    vector <int> ans;
    while(!good.empty()){
        ans.pb(*good.rbegin());
        good.erase(ans.back());
        make_empty(ans.back());
    }
    
    cout << "YES\n";
    reverse(ans.begin(), ans.end());
    for(int i =0 ; i < ans.size(); i++){
        cout << ans[i] << "\n";
    }   
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'void dfs(int, int)':
skyscrapers.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp: In function 'void add(int)':
skyscrapers.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     if(cnt[ind] == st[ind].size()) B[ind] = true;
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void recount_regions(int)':
skyscrapers.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if(cnt[ind] == st[ind].size()) B[ind] = true;
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void union_sets(int, int)':
skyscrapers.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < vv[b].size(); i++){
      |                    ~~^~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void make_empty(int)':
skyscrapers.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for(int j = 0; j < d.size(); j++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for(int i = 0; i <empt.size(); ++i){
      |                    ~~^~~~~~~~~~~~
skyscrapers.cpp:176:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for(int j = 0; j < d.size(); j++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:194:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     for(int i =0 ; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30040 KB ans=YES N=1
2 Correct 15 ms 30036 KB ans=YES N=4
3 Correct 16 ms 30036 KB ans=NO N=4
4 Correct 12 ms 30036 KB ans=YES N=5
5 Correct 13 ms 30012 KB ans=YES N=9
6 Correct 13 ms 29992 KB ans=YES N=5
7 Correct 17 ms 30028 KB ans=NO N=9
8 Correct 16 ms 30040 KB ans=NO N=10
9 Correct 14 ms 30020 KB ans=YES N=10
10 Correct 17 ms 30036 KB ans=YES N=10
11 Correct 13 ms 30036 KB ans=YES N=10
12 Correct 13 ms 30100 KB ans=YES N=9
13 Correct 13 ms 30056 KB ans=YES N=9
14 Correct 16 ms 30096 KB ans=YES N=8
15 Correct 13 ms 30036 KB ans=YES N=8
16 Correct 12 ms 30036 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30040 KB ans=YES N=1
2 Correct 15 ms 30036 KB ans=YES N=4
3 Correct 16 ms 30036 KB ans=NO N=4
4 Correct 12 ms 30036 KB ans=YES N=5
5 Correct 13 ms 30012 KB ans=YES N=9
6 Correct 13 ms 29992 KB ans=YES N=5
7 Correct 17 ms 30028 KB ans=NO N=9
8 Correct 16 ms 30040 KB ans=NO N=10
9 Correct 14 ms 30020 KB ans=YES N=10
10 Correct 17 ms 30036 KB ans=YES N=10
11 Correct 13 ms 30036 KB ans=YES N=10
12 Correct 13 ms 30100 KB ans=YES N=9
13 Correct 13 ms 30056 KB ans=YES N=9
14 Correct 16 ms 30096 KB ans=YES N=8
15 Correct 13 ms 30036 KB ans=YES N=8
16 Correct 12 ms 30036 KB ans=NO N=2
17 Correct 17 ms 30036 KB ans=YES N=17
18 Correct 13 ms 30032 KB ans=YES N=25
19 Incorrect 15 ms 30044 KB Each cell must be removed exactly once
20 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30040 KB ans=YES N=1
2 Correct 15 ms 30036 KB ans=YES N=4
3 Correct 16 ms 30036 KB ans=NO N=4
4 Correct 12 ms 30036 KB ans=YES N=5
5 Correct 13 ms 30012 KB ans=YES N=9
6 Correct 13 ms 29992 KB ans=YES N=5
7 Correct 17 ms 30028 KB ans=NO N=9
8 Correct 16 ms 30040 KB ans=NO N=10
9 Correct 14 ms 30020 KB ans=YES N=10
10 Correct 17 ms 30036 KB ans=YES N=10
11 Correct 13 ms 30036 KB ans=YES N=10
12 Correct 13 ms 30100 KB ans=YES N=9
13 Correct 13 ms 30056 KB ans=YES N=9
14 Correct 16 ms 30096 KB ans=YES N=8
15 Correct 13 ms 30036 KB ans=YES N=8
16 Correct 12 ms 30036 KB ans=NO N=2
17 Correct 17 ms 30036 KB ans=YES N=17
18 Correct 13 ms 30032 KB ans=YES N=25
19 Incorrect 15 ms 30044 KB Each cell must be removed exactly once
20 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30164 KB ans=NO N=1934
2 Correct 19 ms 30184 KB ans=NO N=1965
3 Incorrect 41 ms 30676 KB Each cell must be removed exactly once
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30040 KB ans=YES N=1
2 Correct 15 ms 30036 KB ans=YES N=4
3 Correct 16 ms 30036 KB ans=NO N=4
4 Correct 12 ms 30036 KB ans=YES N=5
5 Correct 13 ms 30012 KB ans=YES N=9
6 Correct 13 ms 29992 KB ans=YES N=5
7 Correct 17 ms 30028 KB ans=NO N=9
8 Correct 16 ms 30040 KB ans=NO N=10
9 Correct 14 ms 30020 KB ans=YES N=10
10 Correct 17 ms 30036 KB ans=YES N=10
11 Correct 13 ms 30036 KB ans=YES N=10
12 Correct 13 ms 30100 KB ans=YES N=9
13 Correct 13 ms 30056 KB ans=YES N=9
14 Correct 16 ms 30096 KB ans=YES N=8
15 Correct 13 ms 30036 KB ans=YES N=8
16 Correct 12 ms 30036 KB ans=NO N=2
17 Correct 17 ms 30036 KB ans=YES N=17
18 Correct 13 ms 30032 KB ans=YES N=25
19 Incorrect 15 ms 30044 KB Each cell must be removed exactly once
20 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 42956 KB ans=NO N=66151
2 Correct 59 ms 34536 KB ans=NO N=64333
3 Incorrect 1389 ms 51812 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 18 ms 30164 KB ans=NO N=1934
2 Correct 19 ms 30184 KB ans=NO N=1965
3 Incorrect 41 ms 30676 KB Each cell must be removed exactly once
4 Halted 0 ms 0 KB -