//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
struct Point {
int x, y;
};
const int nax = 100 * 1000 + 10;
int n, w;
Point pts[nax];
pi walls[nax * 2];
vi events[nax];
int p[400 * 1000 + 10], siz[400 * 1000 + 10];
pi G[nax][4];
int Fund(int x) {
if(p[x] != x) {
p[x] = Fund(p[x]);
}
return p[x];
}
void Onion(int a, int b) {
a = Fund(a), b = Fund(b);
if(a == b) return;
if(siz[a] < siz[b]) swap(a, b);
p[b] = a;
siz[a] += siz[b];
}
struct Node {
int mi, mx, g;
bool act;
};
Node T[(1 << 18)];
map<int,int>sc;
int roz;
void putTag(int v, int x) {
T[v].act = true;
T[v].mi = T[v].mx = T[v].g = x;
}
void push(int v) {
if(!T[v].act) return;
putTag(v << 1, T[v].g);
putTag(v << 1 | 1, T[v].g);
T[v].act = 0;
}
void pull(int v) {
T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi);
T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx);
}
void upd(int a, int b, int x, bool modify = 1, int l = 0, int r = roz - 1, int v = 1) {
if(a <= l && r <= b && T[v].mx == T[v].mi) {
// merge (x << 1, T[v].mx)
if(!modify) {
// cerr << "merging: " << (x << 1) << " with " << T[v].mx << "\n";
Onion(x << 1, T[v].mx);
} else {
if(modify) putTag(v, x << 1 | 1);
}
return;
}
int mid = (l + r) >> 1;
push(v);
if(a <= mid) upd(a, b, x, modify, l, mid, v << 1);
if(mid < b) upd(a, b, x, modify, mid + 1, r, v << 1 | 1);
pull(v);
}
bool vis[(1 << 19)];
void walk(int x, int dir) {
int id = G[x][dir].ND;
vis[G[x][dir].ND] = true;
x = G[x][dir].ST;
dir = (dir + 1) % 4;
while(G[x][dir].ST == 0) {
dir = (dir + 3) % 4;
}
if(!vis[G[x][dir].ND]) {
Onion(id, G[x][dir].ND);
// cerr << "polygon : " << id << " with " << G[x][dir].ND << " " << dir << "\n";
walk(x, dir);
}
}
vi V[(1 << 19)];
int dist[(1 << 19)];
void bfs(int x) {
for(int i = 0; i <= 2 * w + 1; ++i) {
vis[i] = false;
}
queue<int>Q;
Q.push(x);
vis[x] = true;
while(!Q.empty()) {
x = Q.front();
Q.pop();
// cerr << "DIST: " << x << " " << dist[x] << "\n";
for(int y : V[x]) {
if(!vis[y]) {
dist[y] = dist[x] + 1;
vis[y] = true;
Q.push(y);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int x, y, i = 1; i <= n; ++i) {
cin >> x >> y;
pts[i] = {x, y};
sc[y];
}
for(auto &it : sc) it.ND = roz++;
int num = 0;
for(int i = 1; i <= n; ++i) pts[i].y = sc[pts[i].y];
sc.clear();
for(int i = 1; i <= n; ++i) sc[pts[i].x];
for(auto &it : sc) it.ND = num++;
for(int i = 1; i <= n; ++i) pts[i].x = sc[pts[i].x];
cin >> w;
siz[0] = 1;
for(int a, b, i = 1; i <= w; ++i) {
cin >> a >> b;
if(pts[a].x == pts[b].x) {
events[pts[a].x].PB(i);
if(pts[a].y > pts[b].y) swap(a, b);
G[a][0] = {b, i << 1 | 1};
G[b][2] = {a, i << 1};
} else {
if(pts[a].x > pts[b].x) {
swap(a, b);
}
G[a][1] = {b, i << 1 | 1};
G[b][3] = {a, i << 1};
}
walls[i] = {a, b};
p[i << 1] = (i << 1);
p[i << 1 | 1] = (i << 1 | 1);
siz[i << 1] = siz[i << 1 | 1] = 1;
}
// cerr << "SHOW GRAPH\n";
// for(int i = 1; i <= n; ++i) {
// for(int d = 0; d < 4; ++d) {
// if(G[i][d].ST != 0) {
// cerr << i << " " << d << ": " << G[i][d].ST << " " << G[i][d].ND << "\n";
// }
// }
// }
for(int i = 0; i < num ; ++i) {
for(auto &id : events[i]) {
upd(pts[walls[id].ST].y, pts[walls[id].ND].y - 1, id, 0);
}
for(auto &id : events[i]) {
upd(pts[walls[id].ST].y, pts[walls[id].ND].y - 1, id, 1);
}
}
for(int i = 1; i <= n; ++i) {
for(int d = 0; d < 4; ++d) {
if(G[i][d].ST != 0 && !vis[G[i][d].ND]) {
walk(i, d);
}
}
}
for(int i = 1; i <= w; ++i) {
V[Fund(i << 1)].PB(Fund(i << 1 | 1));
V[Fund(i << 1 | 1)].PB(Fund(i << 1));
}
bfs(Fund(0));
vi ans = {};
for(int i = 1; i <= w; ++i) {
if(dist[Fund(i << 1)] == dist[Fund(i << 1 | 1)]) {
ans.PB(i);
}
}
cout << (int)ans.size() << "\n";
for(int x : ans) {
cout << x << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
14932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
14944 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14932 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
15020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
15060 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
15060 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
14932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15104 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15008 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
18164 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
124 ms |
25252 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
124 ms |
28492 KB |
Output is correct |
| 2 |
Correct |
175 ms |
30692 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
154 ms |
29084 KB |
Output is correct |
| 2 |
Runtime error |
233 ms |
33428 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
206 ms |
30548 KB |
Output is correct |
| 2 |
Correct |
175 ms |
30784 KB |
Output is correct |
