oj.uz

Submission #855525

# Submission time Handle Problem Language Result Execution time Memory
855525 2023-10-01T11:36:30 Z mychecksedad Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 3500 ms 630328 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 22;

struct Dsu {
  vector<int> s, p;
  int sz;
  Dsu(int n){
    sz = n;
    s.resize(n+1, 1);
    p.resize(n+1);
    for(int i = 0; i <= n; ++i) p[i] = i;
  }
  int find(int v){
    if(p[v] == v) return v;
    return (p[v] = find(p[v]));
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]){
        swap(a, b);
      }
      s[b] += s[a];
      p[a] = b;
      sz--;
    }
  }
};

int n, t, b[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
array<int, 2> a[N];
vector<int> g[N];
map<array<int, 2>, int> A;
vector<bool> active, vis;

vector<int> bfs(int s){
  queue<int> q; q.push(s);
  vector<int> vv;
  vis[s] = 1;
  while(!q.empty()){
    int v = q.front(); q.pop();
    vv.pb(v);
    for(int u: g[v]) if(!vis[u] && active[u]) q.push(u), vis[u] = 1;
  }
  return vv;
}

vector<int> calc(vector<int> al){
  if(al.empty()) return {};

  sort(all(al));
  
  int v = al.back();
  
  vis.clear();
  vis.resize(n+1, 0);
  
  vis[v] = 1;
  
  vector<vector<int>> comp;

  for(int u: g[v]){
    if(!vis[u] && active[u]) comp.pb(bfs(u));
  }
  
  active[v] = 0;
  if(comp.size() <= 1){
    al.pop_back();
    vector<int> clc = calc(al);
    clc.pb(v);
    return clc;
  }

  vector<vector<int>> answers;
  for(auto vv: comp) answers.pb(calc(vv));

  sort(all(answers), [&](const vector<int> &x, const vector<int> &y){
    return x.back() < y.back();
  });
  
  vector<int> res;
  
  int i = 0;
  for(auto vv: answers){
    if(i == 1)
      res.pb(v);
    for(auto x: vv) res.pb(x);
    ++i;
  }
  return res;
}

void solve(){
  cin >> n >> t;
  for(int i = 1; i <= n; ++i){
    cin >> a[i][0] >> a[i][1];
    A[a[i]] = i;
  }
  Dsu d(n);
  for(int i = 1; i <= n; ++i){
    for(int j = 0; j < 8; ++j){
      int x = a[i][0] + b[j][0];
      int y = a[i][1] + b[j][1];
      if(A[{x, y}] > 0)
        g[i].pb(A[{x, y}]), d.merge(i, A[{x, y}]);
    }
  }
  if(d.sz > 1){
    cout << "NO\n";
    return;
  }
  cout << "YES\n";

  // for(int i = 1; i <= n; ++i){
  //   for(int u: g[i]) cout << u << ' ';
  //   en;
  // }

  active.resize(n + 1, 1);
  vector<int> al;
  for(int i = 1; i <= n; ++i) al.pb(i);
  vector<int> ans = calc(al);
  assert(ans.size() == n);
  for(int k: ans) cout << k << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from skyscrapers.cpp:2:
skyscrapers.cpp: In function 'void solve()':
skyscrapers.cpp:132:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |   assert(ans.size() == n);
      |          ~~~~~~~~~~~^~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:139:15: warning: unused variable 'aa' [-Wunused-variable]
  139 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26204 KB ans=NO N=1934
2 Correct 9 ms 25688 KB ans=NO N=1965
3 Incorrect 92 ms 38312 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 5 ms 25176 KB ans=YES N=1
2 Correct 5 ms 25180 KB ans=YES N=4
3 Correct 5 ms 25212 KB ans=NO N=4
4 Correct 6 ms 25180 KB ans=YES N=5
5 Correct 5 ms 25180 KB ans=YES N=9
6 Correct 7 ms 25180 KB ans=YES N=5
7 Correct 6 ms 25180 KB ans=NO N=9
8 Correct 5 ms 25180 KB ans=NO N=10
9 Correct 5 ms 25180 KB ans=YES N=10
10 Incorrect 5 ms 25180 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 34824 KB ans=NO N=66151
2 Correct 218 ms 54720 KB ans=NO N=64333
3 Execution timed out 3565 ms 630328 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26204 KB ans=NO N=1934
2 Correct 9 ms 25688 KB ans=NO N=1965
3 Incorrect 92 ms 38312 KB Full cells must be connected
4 Halted 0 ms 0 KB -