#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
int X[100100],Y[100100],lev[400100],side[100100][4][2],Xof[400100];
bitset<400100>vis;
vector<int> adj[400100];
void AE(int a,int b){
adj[a].push_back(b);
adj[b].push_back(a);
}
set<pair<int,int>>st;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,w;
cin>>n;
for(int i=1;i<=n;i++)
cin>>X[i]>>Y[i];
cin>>w;
for(int i=1;i<=w;i++){
int a,b;
cin>>a>>b;
if(X[a]==X[b]){
if(Y[a]>Y[b])swap(a,b);
side[a][2][1]=i;
side[a][2][0]=i+w;
side[b][0][0]=i;
side[b][0][1]=i+w;
Xof[i]=X[a];
st.insert({Xof[i],i});
} else {
if(X[a]>X[b])swap(a,b);
side[a][1][0]=i;
side[a][1][1]=i+w;
side[b][3][1]=i;
side[b][3][0]=i+w;
Xof[i]=1e9;
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<4;j++) if(side[i][j][1])
for(int k=(j+1)%4;;k=(k+1)%4) if(side[i][k][0]){
AE(side[i][k][0],side[i][j][1]);break;}
deque<int>Q;
memset(lev,7,sizeof lev);
while(1){
if(st.empty())break;
int K=st.begin()->second;
Q.push_back(K);
lev[K]=0;
while(Q.size()){
int x=Q.front();Q.pop_front();
if(vis[x])continue;
if(x<=w)st.erase({Xof[x],x});
vis[x]=1;
for(auto y:adj[x])
if(lev[y]>lev[x])
Q.push_front(y),lev[y]=lev[x];
adj[x].clear();
int k=(x>w?x-w:x+w);
if(lev[k]>lev[x]+1)
lev[k]=lev[x]+1,Q.push_back(k);
}
}
vector<int>v;
for(int i=1;i<=w;i++)
if(lev[i]==lev[i+w])
v.push_back(i);
cout<<v.size()<<'\n';
for(auto i:v)
cout<<i<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11356 KB |
Output is correct |
2 |
Correct |
5 ms |
11356 KB |
Output is correct |
3 |
Correct |
6 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
11608 KB |
Output is correct |
2 |
Correct |
6 ms |
11352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11356 KB |
Output is correct |
2 |
Correct |
5 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11332 KB |
Output is correct |
2 |
Correct |
8 ms |
11480 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11356 KB |
Output is correct |
2 |
Correct |
5 ms |
11356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
14360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
22024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
22992 KB |
Output is correct |
2 |
Correct |
164 ms |
28604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
180 ms |
26356 KB |
Output is correct |
2 |
Correct |
206 ms |
29012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
212 ms |
28744 KB |
Output is correct |
2 |
Correct |
70 ms |
22984 KB |
Output is correct |