Submission #855522

#TimeUsernameProblemLanguageResultExecution timeMemory
855522mychecksedadBuilding Skyscrapers (CEOI19_skyscrapers)C++17
0 / 100
3215 ms477664 KiB
/* 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: answers) 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 (stderr)

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;
      |               ^~
#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...