Submission #571123

#TimeUsernameProblemLanguageResultExecution timeMemory
571123webBuilding Skyscrapers (CEOI19_skyscrapers)C++17
54 / 100
1620 ms19164 KiB
#include <functional> #include <queue> #include <bitset> #include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; typedef long long ll; vector<bitset<2*1000000001>> grid; void setBits(int x,int y) { for(int i = x-1; i<= x+1; ++i) { for(int j = y-1; j<= y+1; ++j) { grid[x].set(y); } } } bool isAdjacent(pair<long, pair<long, int>>s1, pair<long, pair<long, int>>s2) { return abs(s1.first -s2.first ) <= 1 && abs(s1.second.first - s2.second.first) <=1;} bitset<150000> visited; vector<vector<int>> adjList; vector<pair<long,pair<long, int>>> buildings; vector<int> order; long calcManhattenDist(int i, int j) { return abs(buildings[i].first - buildings[j].first) + abs(buildings[i].second.first - buildings[j].second.first); } void BFS(int startNode) { auto comp = [startNode](int lhs, int rhs) { return buildings[lhs] > buildings[rhs];//calcManhattenDist(startNode, lhs) > calcManhattenDist(startNode, rhs); }; priority_queue<int, vector<int>, decltype( comp)> nodeList(comp); nodeList.push(startNode); visited.set(startNode); while(nodeList.size() != 0) { int newNode = nodeList.top(); nodeList.pop(); order.push_back(newNode); for(auto node:adjList[newNode]) { if(!visited.test(node)) { nodeList.push(node); visited.set(node); } } } } int main() { int n; cin>>n; int t; cin>>t; buildings.resize(n); for(int i = 0; i<n; ++i) { long a; long b; cin>>a>>b; buildings[i] = {a,{b, i}}; } adjList.resize(n); sort(buildings.begin(), buildings.end()); for(int i = 0; i<n-1; ++i) { for(int j = i+1; j<n; ++j) { if(buildings[j].first - buildings[i].first > 1) break; else { if(isAdjacent(buildings[i], buildings[j])) { adjList[i].push_back(j); adjList[j].push_back(i); } } } } //DFS BFS(0); for(int i = 0; i<n; ++i) { if(!visited.test(i)) { cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; for(int i = 0; i<n; ++i) { cout<<buildings[order[i]].second.second+1<<endl; } return 0; }
#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...