Submission #799474

#TimeUsernameProblemLanguageResultExecution timeMemory
799474Ronin13Building Skyscrapers (CEOI19_skyscrapers)C++17
0 / 100
386 ms28740 KiB
#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 = 200001; 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 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); 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); vv[a].pb(x); } p[b] = a; out[a] |= out[b]; } 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 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]; 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(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 (stderr)

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 union_sets(int, int)':
skyscrapers.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < vv[b].size(); i++){
      |                    ~~^~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void recount_regions(int)':
skyscrapers.cpp:93: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]
   93 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(cnt[ind] == st[ind].size()) B[ind] = true;
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void make_empty(int)':
skyscrapers.cpp:110: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]
  110 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:114: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]
  114 |     for(int i = 0; i < d.size(); i++){
      |                    ~~^~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:149: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]
  149 |         for(int j = 0; j < d.size(); j++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:165: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]
  165 |     for(int i = 0; i <empt.size(); ++i){
      |                    ~~^~~~~~~~~~~~
skyscrapers.cpp:167: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]
  167 |         for(int j = 0; j < d.size(); j++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:184:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |     for(int i =0 ; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...