#include <bits/stdc++.h>
#include <parks.h>
using namespace std;
struct Edge {
int from , to , cost;
bool operator<(const Edge &autre){
if(from == autre.from){
return to < autre.to;
}
return from < autre.from;
}
};
const int N = 1e5 * 2 + 10;
int p[N];
int sz[N];
void make(int a){
p[a] = a;
sz[a] = 0;
return ;
}
int find_set(int a){
if(p[a] == a) return a;
return p[a] = find_set(p[a]);
}
bool union_sets(int a , int b){
a = find_set(a);
b = find_set(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
return true;
}
const int dx[4] = {2 , 0 , 0 , -2} , dy[4] = {0 , 2 , -2 , 0};
int construct_roads(vector<int> x , vector<int> y){
int n = (int)x.size();
vector<Edge> v;
map<pair<int,int> , int> seen;
map<int , pair<int,int>> after;
for(int i = 0 ; i < n ; i++){
seen[make_pair(x[i] , y[i])] = i + 1;
after[i] = make_pair(x[i] , y[i]);
}
for(int i = 0 ; i < n ; i++){
v.push_back({x[i] , y[i] , i});
}
for(int i = 0 ; i < n ; i++){
make(i);
}
sort(v.begin(), v.end());
// first we see if an answer exists
vector<int> u , q;
for(int i = 0 ; i < n ; i++){
bool ok = false;
for(int j = 0 ; j < 4 ; j++){
int new_x = x[i] + dx[j];
int new_y = y[i] + dy[j];
int m = seen[make_pair(new_x , new_y)];
if(m){
m--;
ok = true;
if(union_sets(i , m)){
u.emplace_back(i);
q.emplace_back(m);
}
}
}
if(!ok) return 0;
}
map<pair<int,int> , bool> used;
vector<int> one , two;
for(int i = 0 ; i < (int)u.size() ; i++){
int now_t = u[i] , now_z = q[i];
auto pq = after[now_t] , r = after[now_z];
pair<int,int> choice1 , choice2;
if(pq.first == r.first){
choice1 = make_pair(pq.first - 1 , (pq.second+r.second)/2);
choice2 = make_pair(pq.first + 1 , (pq.second+r.second)/2);
}
else{
assert(pq.second == r.second);
choice1 = make_pair((pq.first + r.first)/2 , pq.second - 1);
choice2 = make_pair((pq.first + r.first) / 2 , pq.second + 1);
}
if(used[choice1]){
assert(!used[choice2]);
one.emplace_back(choice2.first);
two.emplace_back(choice2.second);
}
else{
assert(!used[choice1]);
one.emplace_back(choice1.first);
two.emplace_back(choice1.second);
}
}
build(u , q , one , two);
//debug(u , q , one , two);
return 1;
}
/*int main(){
int n;
cin >> n;
vector<int> x(n), y(n);
for(int i = 0 ; i < n ; i++){
cin >> x[i];
}
for(int i = 0 ; i < n ; i++){
cin >> y[i];
}
cout << construct_roads(x , y);
return 0;
} */
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
