#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
const int MAXW = 2e5;
int uf[2*MAXW]; // for vertical lines, left is +0, right is +w. For horizontal, bottom is +0, top is +w
set<pii> active_points;
char point_mask[MAXN]; // right, up, left, down
pii points[MAXN];
int windex[MAXN][4];
int n, w;
vector<int> edges[2*MAXW];
pii walls[MAXW];
vector<pii> w_edges[MAXN];
bool deact[MAXW];
vector<int> standing;
int deg[MAXN];
int dist[2*MAXW];
int find(int i) {
return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}
void mask_add(int cur, int other, int w) {
if (points[other].first > points[cur].first) {
point_mask[cur] += 1;
windex[cur][0] = w;
}
if (points[other].second > points[cur].second) {
point_mask[cur] += 2;
windex[cur][1] = w;
}
if (points[other].first < points[cur].first) {
point_mask[cur] += 4;
windex[cur][2] = w;
}
if (points[other].second < points[cur].second) {
point_mask[cur] += 8;
windex[cur][3] = w;
}
}
int shift(int mask, int s) {
int rshift = mask >> s;
int lshift = mask % (1 << s);
return (lshift << (4-s)) + rshift;
}
int get_cc(int i, int bit) {
int base = windex[i][bit];
if (bit == 1 || bit == 2) return base;
return base+w;
}
int get_cw(int i, int bit) {
return (get_cc(i, bit)+w)%(2*w);
}
void prune(int cur) {
deg[cur] = 0;
for (pii next: w_edges[cur]) {
if (deact[next.second]) continue;
deact[next.second] = 1;
deg[next.first]--;
if (deg[next.first] == 1) prune(next.first);
}
}
void bfs(int s) {
dist[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int next: edges[cur]) {
if (dist[next] != -1) continue;
dist[next] = dist[cur]+1;
q.push(next);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
points[i] = pii(x, y);
}
cin >> w;
fill(uf, uf+2*w, -1);
for (int i = 0; i < w; i++) {
int x, y; cin >> x >> y;
x--; y--;
walls[i] = pii(x, y);
w_edges[x].push_back(pii(y, i));
w_edges[y].push_back(pii(x, i));
deg[x]++;
deg[y]++;
}
for (int i = 0; i < n; i++)
if (deg[i] == 1) prune(i);
for (int i = 0; i < w; i++) {
if (deact[i]) {
standing.push_back(i);
continue;
}
int x = walls[i].first;
int y = walls[i].second;
active_points.insert(pii(points[x].first, x));
active_points.insert(pii(points[y].first, y));
mask_add(x, y, i);
mask_add(y, x, i);
}
for (pii p: active_points) {
int i = p.second;
for (int bit = 0; bit < 4; bit++) {
if ((point_mask[i] & (1 << bit)) == 0) continue;
int ccval = get_cc(i, bit);
int maskcpy = shift(point_mask[i], bit+1); // shift to the right
int nbit = log2(maskcpy&(-maskcpy));
nbit = (nbit+bit+1)%4;
int cwval = get_cw(i, nbit);
int ida = find(ccval);
int idb = find(cwval);
if (ida != idb) uf[ida] = idb;
}
}
for (int i = 0; i < w; i++) {
if (deact[i]) continue;
int a = find(i);
int b = find(w+i);
//assert(a != b); // wouldve been deactivated
if (a == b) continue;
edges[a].push_back(b);
edges[b].push_back(a);
}
fill(dist, dist+2*w, -1);
for (pii p: active_points) {
int i = p.second;
int bit = log2(point_mask[i] & (-point_mask[i]));
if (dist[find(get_cc(i, bit))] != -1) continue;
assert((point_mask[i] & 2) || (point_mask[i] & 8));
if (point_mask[i] & 2) {
int out = get_cc(i, 1);
bfs(find(out));
}
else {
int out = get_cw(i, 3);
bfs(find(out));
}
}
for (int i = 0; i < w; i++) {
if (deact[i]) continue;
int a = find(i);
int b = find(w+i);
if (dist[a] == dist[b]) standing.push_back(i);
}
cout << standing.size() << '\n';
for (int i: standing) cout << (i+1) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12076 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12116 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
14848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
22728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
25188 KB |
Output is correct |
| 2 |
Correct |
241 ms |
29832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
27592 KB |
Output is correct |
| 2 |
Correct |
232 ms |
31612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
271 ms |
29608 KB |
Output is correct |
| 2 |
Correct |
89 ms |
24620 KB |
Output is correct |
