Submission #476886

#TimeUsernameProblemLanguageResultExecution timeMemory
476886OzyBuilding Skyscrapers (CEOI19_skyscrapers)C++17
0 / 100
1666 ms1048580 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define lli long long int #define rep(i,a,b) for (int i = (a); i <= (b); i++) #define repa(i,a,b) for (int i = (a); i >= (b); i--) #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define MAX 150000 lli n,t,a,b,act,k,num; map<pair<lli,lli>, lli> mapa; vector<lli> hijos[MAX+2]; lli dir[16] = {-1,0,1,0,-1,1,1,-1,0,1,0,-1,1,1,-1,-1}; lli visitados[MAX+2],dis[MAX+2]; queue<lli> cola; vector<lli> res; void dfs(lli pos) { res.push_back(pos); for(auto h : hijos[pos]) { if (dis[h] <= dis[pos]) continue; dfs(h); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> t; rep(i,1,n) { cin >> a >> b; mapa[{a,b}] = i; rep(o,0,7) { if (mapa.find({a+dir[o],b + dir[o+8]}) != mapa.end()) { k = mapa[{a+dir[o],b + dir[o+8]}]; hijos[k].push_back(i); hijos[i].push_back(k); } } } //correcto cola.push(1); visitados[1] = 1; num = 0; while (!cola.empty()) { act = cola.front(); cola.pop(); num++; for(auto h : hijos[act]) { if (visitados[h] == 1) continue; visitados[h] = 1; dis[h] = dis[act] + 1; cola.push(h); } } if (num < n) { cout << "NO"; return 0; } dfs(1); cout << "YES\n"; for (auto r : res) cout << r << "\n"; }
#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...