#include <bits/stdc++.h>
using namespace std;
int n,w,x[100001],y[100001],a[400001],b[400001],d[400001],nxt[100001][4],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},p[400001],l[100001];
vector <int> safe,ve[100001];
queue <int> q[200002];
int f(int i){
return (l[i]==i?i:l[i]=f(l[i]));
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n;
iota(l,l+n+1,0);
for (int i=1;i<=n;i++)
cin >> x[i] >> y[i];
cin >> w;
for (int i=1;i<=w;i++){
cin >> a[i] >> b[i];
l[f(a[i])]=f(b[i]);
a[i+w]=b[i];
b[i+w]=a[i];
for (int j=0;j<4;j++)
if (abs(dx[j])+abs(x[a[i]]+dx[j]-x[b[i]])==abs(x[a[i]]-x[b[i]])&&abs(dy[j])+abs(y[a[i]]+dy[j]-y[b[i]])==abs(y[a[i]]-y[b[i]])){
d[i]=j;
d[i+w]=(j+2)&3;
nxt[a[i]][j]=i;
nxt[b[i]][d[i+w]]=i+w;
}
}
for (int i=1;i<=n;i++)
ve[f(i)].push_back(i);
for (int i=1;i<=n;i++){
if (ve[i].empty())
continue;
int mx=0;
for (int j:ve[i])
if (!mx||x[mx]>x[j]||(x[mx]==x[j]&&y[mx]<y[j]))
mx=j;
if (!nxt[mx][3])
continue;
q[1].push(nxt[mx][3]);
}
for (int i=1;i<=n*2;i++)
while (!q[i].empty()){
int u=q[i].front();
q[i].pop();
if (p[u])
continue;
p[u]=i;
q[i+1].push((u>w?u-w:u+w));
for (int j=0;j<4;j++)
if (nxt[b[u]][(d[u]+j+3)%4]){
int v=nxt[b[u]][(d[u]+j+3)%4];
q[i].push(v);
break;
}
}
for (int i=1;i<=w;i++)
if (p[i]==p[i+w])
safe.push_back(i);
cout << safe.size() << '\n';
for (int i:safe)
cout << i << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
42 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
27 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
27 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |