#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
map<pair<int, int>, int> f;
vector<pair<int, int>> adj[N];
bool vis[N];
vector<int> active_edges;
map<pair<int, int>, vector<pair<int, int>>> for_2sat;
array<pair<int, int>, 2> pts[N];
vector<int> adj_2sat[2 * N], rev_adj_2sat[2 * N];
int cnt_out[2 * N];
int dfs(int u){
vis[u] = true;
int cnt = 1;
for(auto [to, idx_e]: adj[u]){
if(vis[to]) continue;
cnt += dfs(to);
active_edges.push_back(idx_e);
}
return cnt;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for(int i = 0; i < n; ++i)
f[{x[i], y[i]}] = i;
vector<array<int, 2>> edges;
for(int i = 0; i < n; ++i){
array<int, 2> adj_dir[2]{{2, 0}, {0, 2}};
for(auto [dx, dy]: adj_dir){
auto [to_x, to_y] = pair{dx + x[i], dy + y[i]};
if(f.count({to_x, to_y})){
int idx = f[{to_x, to_y}];
edges.push_back({i, idx});
adj[i].push_back({idx, edges.size() - 1});
adj[idx].push_back({i, edges.size() - 1});
}
}
}
int cnt = dfs(0);
if(cnt != n - 1)
return 0;
for(int i = 0; i < n - 1; ++i){
int idx_e = active_edges[i];
pair<int, int> p1, p2;
int f1 = edges[idx_e][0];
int f2 = edges[idx_e][1];
auto [sx, sy] = pair{x[f1], y[f1]};
auto [dx, dy] = pair{x[f2] - x[f1], y[f2] - y[f1]};
dx /= 2;
dy /= 2;
p1 = {sx + dy, sy + dx};
p2 = {sx - dy, sy - dx};
pts[i] = {p1, p2};
for_2sat[p1].push_back({2 * i, 2 * i + 1});
for_2sat[p2].push_back({2 * i + 1, 2 * i});
}
for(auto [p, v]: for_2sat){
for(int i = 0; i < v.size(); ++i){
for(int j = 0; j < v.size(); ++j){
if(i == j) continue;
adj_2sat[v[i].first].push_back(v[j].second);
rev_adj_2sat[v[j].second].push_back(v[i].first);
}
}
}
queue<int> q;
for(int i = 0; i < 2 * (n - 1); ++i){
cnt_out[i] = adj_2sat[i].size();
if(!cnt_out[i])
q.push(i);
}
vector<int> topsort;
while(!q.empty()){
int u = q.front();
q.pop();
topsort.push_back(u);
for(int to: rev_adj_2sat[u]){
--cnt_out[to];
if(!cnt_out[to])
q.push(to);
}
}
if(topsort.size() != 2 * (n - 1))
return 0;
static int loc[2 * N];
reverse(topsort.begin(), topsort.end());
for(int i = 0; i < 2 * (n - 1); ++i)
loc[topsort[i]] = i;
vector<pair<int, int>> benches;
for(int i = 0; i < (n - 1); ++i){
if(loc[2 * i] < loc[2 * i + 1])
benches.push_back(pts[i][0]);
else
benches.push_back(pts[i][1]);
}
vector<int> u, v, a, b;
for(int i = 0; i < n - 1; ++i){
int idx_e = active_edges[i];
u.push_back(edges[idx_e][0]);
v.push_back(edges[idx_e][1]);
a.push_back(benches[i].first);
b.push_back(benches[i].second);
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < v.size(); ++i){
| ~~^~~~~~~~~~
parks.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int j = 0; j < v.size(); ++j){
| ~~^~~~~~~~~~
parks.cpp:105:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | if(topsort.size() != 2 * (n - 1))
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23808 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
