Submission #434992

#TimeUsernameProblemLanguageResultExecution timeMemory
434992model_codeFountain Parks (IOI21_parks)C++17
30 / 100
4075 ms30208 KiB
/** * Task: parks * Author: Kian Mirjalali * Solution: Solution based on chessboard coloring of cells (trees) * Time: O(n) on average * It uses a hash map to find the index of a vertex by its coordinate. * The solution is correct but it will become slow on some inputs due to the bad hash function. */ #include "parks.h" #include <complex> #include <unordered_map> using namespace std; #define tpc(C) template<class C> #define allOf(c) ((c).begin()), ((c).end()) #define fori(i, a, b) for (int i = (a); i < int(b); i++) #define forn(i, n) fori(i, 0, (n)) #define dbg(x) #x << "=" << (x) #define show(x) cerr << dbg(x) << endl tpc(C) inline int sz(const C& c) { return c.size(); } typedef vector<int> VI; typedef complex<int> Point; #define X real() #define Y imag() ///////////////////////// const Point MOVES[] = { {-2, 0}, {+2, 0}, {0, -2}, {0, +2}, }; const int LEFT = 0; const int RIGHT = 1; const int UP = 3; ///////////////////////// struct PointHash { inline size_t operator()(const Point &a) const { auto h = hash<int>(); return h(a.X) ^ h(a.Y); // XOR is not a good hash function } }; class Point2Index { unordered_map<Point, int, PointHash> p2i; public: inline Point2Index() { } inline void put(const Point& p, int i) { p2i[p] = i; } inline int get(const Point& p) const { auto it = p2i.find(p); return (it == p2i.end()) ? -1 : it->second; } inline bool contains(const Point& p) const { return p2i.find(p) != p2i.end(); } }; ///////////////////////// VI q, mark; inline void enq(int x) { if (mark[x]) return; mark[x] = true; q.push_back(x); } ///////////////////////// int construct_roads(VI x, VI y) { int n = x.size(); vector<Point> vertex(n); Point2Index v2i; forn(i, n) { vertex[i] = Point(x[i], y[i]); v2i.put(vertex[i], i); } {// Check connectivity q.clear(); q.reserve(n); mark.assign(n, false); enq(0); for (int tail = 0; tail < sz(q); tail++) { Point p = vertex[q[tail]]; for (auto& mov : MOVES) { int nei = v2i.get(p+mov); if (nei >= 0) enq(nei); } } if (sz(q) != n) return 0; } VI u, v, a, b; forn(i, n) { Point pi = vertex[i]; bool is_white_cell = (((pi.X+pi.Y)&2) == 0); { Point pj = pi + MOVES[RIGHT]; int j = v2i.get(pj); if ((j >= 0) && !(v2i.contains(pi+MOVES[UP]) && v2i.contains(pj+MOVES[UP]) && is_white_cell)) { u.push_back(i); v.push_back(j); a.push_back(pi.X+1); b.push_back(pi.Y+(is_white_cell?+1:-1)); } } { Point pj = pi + MOVES[UP]; int j = v2i.get(pj); if ((j >= 0) && !(v2i.contains(pi+MOVES[LEFT]) && v2i.contains(pj+MOVES[LEFT]) && is_white_cell)) { u.push_back(i); v.push_back(j); a.push_back(pi.X+(is_white_cell?-1:+1)); b.push_back(pi.Y+1); } } } build(u, v, a, b); return 1; }
#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...