#include "parks.h" #include<bits/stdc++.h> using namespace std; vector<int>x, y; int n; namespace sub1{ int solve(){ vector<int>p(n); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&] (int i, int j){ return y[i] < y[j]; }); vector<int>u, v, a, b; for(int i = 1; i < n; i++){ if(y[p[i]] > y[p[i - 1]] + 2){ return 0; } u.push_back(p[i - 1]); v.push_back(p[i]); a.push_back(1); b.push_back(y[p[i]] - 1); } build(u, v, a, b); return 1; } } namespace sub2{ int solve(){ vector<map<int, int>>id(2); for(int i = 0; i < n; i++){ id[(x[i] - 1) >> 1][y[i]] = i; } vector<pair<int, int>>edge; auto create_edge = [&] (int i, int x, int y){ if(x == 0){ return; } auto it = id[x = (x - 1) >> 1].find(y); if(it != id[x].end()){ edge.push_back(make_pair(i, it->second)); } }; for(int i = 0; i < n; i++){ create_edge(i, x[i] - 2, y[i]); create_edge(i, x[i], y[i] - 2); } vector<int>lab(n); iota(lab.begin(), lab.end(), 0); auto find_set = [&] (int i){ while(i != lab[i]){ i = lab[i] = lab[lab[i]]; } return i; }; function<bool(int, int)>merge = [&] (int i, int j){ if((i = find_set(i)) != (j = find_set(j))){ lab[i] = j; return true; } return false; }; vector<int>u, v, a, b; for(auto& [i, j] : edge){ if(merge(i, j)){ u.push_back(i); v.push_back(j); if(x[i] == x[j]){ a.push_back(x[i] == 2 ? 1 : 5); b.push_back(max(y[i], y[j]) - 1); } else{ a.push_back(3); b.push_back(y[i] - 1); } } } if(u.size() != n - 1){ return 0; } build(u, v, a, b); return 1; } } namespace sub3{ int solve(){ vector<map<int, int>>id(3); for(int i = 0; i < n; i++){ id[(x[i] - 1) >> 1][y[i]] = i; } vector<pair<int, int>>edge; auto create_edge = [&] (int i, int x, int y){ if(x == 0){ return; } auto it = id[x = (x - 1) >> 1].find(y); if(it != id[x].end()){ edge.push_back(make_pair(i, it->second)); } }; for(int i = 0; i < n; i++){ create_edge(i, x[i] - 2, y[i]); create_edge(i, x[i], y[i] - 2); } vector<int>lab(n); iota(lab.begin(), lab.end(), 0); auto find_set = [&] (int i){ while(i != lab[i]){ i = lab[i] = lab[lab[i]]; } return i; }; function<bool(int, int)>merge = [&] (int i, int j){ if((i = find_set(i)) != (j = find_set(j))){ lab[i] = j; return true; } return false; }; vector<int>u, v, a, b; sort(edge.begin(), edge.end(), [&] (pair<int, int>i, pair<int, int>j){ return min(make_pair(x[i.first], y[i.first]), make_pair(x[i.second], y[i.second])) < min(make_pair(x[j.first], y[j.first]), make_pair(x[j.second], y[j.second])); }); map<pair<int, int>, bool>vis; for(auto& [i, j] : edge){ if(merge(i, j)){ u.push_back(i); v.push_back(j); if(x[i] == x[j]){ if(x[i] == 2 || x[i] == 6){ a.push_back(x[i] == 2 ? 1 : 7); } else if(!vis[make_pair(3, max(y[i], y[j]) - 1)]){ vis[make_pair(3, max(y[i], y[j]) - 1)] = true; a.push_back(3); } else{ vis[make_pair(5, max(y[i], y[j]) - 1)] = true; a.push_back(5); } b.push_back(max(y[i], y[j]) - 1); } else{ int X = max(x[i], x[j]) - 1; a.push_back(X); if(!vis[make_pair(X, y[i] - 1)]){ vis[make_pair(X, y[i] - 1)] = true; b.push_back(y[i] - 1); } else{ vis[make_pair(X, y[i] + 1)] = true; b.push_back(y[i] + 1); } } } } if(u.size() != n - 1){ return 0; } build(u, v, a, b); return 1; } } namespace sub456{ int solve(){ vector<int>lab(n); iota(lab.begin(), lab.end(), 0); auto find_set = [&] (int i){ while(i != lab[i]){ i = lab[i] = lab[lab[i]]; } return i; }; function<bool(int, int)>merge = [&] (int i, int j){ if((i = find_set(i)) != (j = find_set(j))){ lab[i] = j; return true; } return false; }; vector<int>p(n); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&] (int i, int j){ return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]); }); map<pair<int, int>, int>id; for(int i = 0; i < n; i++){ id[make_pair(x[i], y[i])] = i; } vector<int>u, v, a, b; for(int& i : p){ auto it = id.find(make_pair(x[i], y[i] + 2)); if(it != id.end()){ int p = it->second; if(merge(i, p)){ if(~((x[i] >> 1) + (y[i] >> 1)) & 1){ a.push_back(x[i] - 1); } else{ a.push_back(x[i] + 1); } b.push_back(y[i] + 1); u.push_back(i); v.push_back(p); } } if((it = id.find(make_pair(x[i] + 2, y[i]))) != id.end()){ int p = it->second; if(find_set(i) != find_set(p)){ if(((x[i] >> 1) + (y[i] >> 1)) & 1){ if(id.find(make_pair(x[i], y[i] - 2)) != id.end() && id.find(make_pair(x[i] + 2, y[i] - 2)) != id.end()){ continue; } b.push_back(y[i] - 1); } else{ b.push_back(y[i] + 1); } a.push_back(x[i] + 1); u.push_back(i); v.push_back(p); merge(i, p); } } } if(u.size() != n - 1){ return 0; } build(u, v, a, b); return 1; } } int construct_roads(vector<int>_x, vector<int>_y){ swap(x, _x); swap(y, _y); n = x.size(); if(*max_element(x.begin(), x.end()) == 2){ return sub1::solve(); } if(*max_element(x.begin(), x.end()) <= 4){ return sub2::solve(); } if(*max_element(x.begin(), x.end()) <= 6){ return sub3::solve(); } return sub456::solve(); }