#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
int tree[4*(N+5)];
array<int,2> points[N];
array<int,3> hot_pos[4*N];
array<int,2> walls[2*N];
array<int,2> wall_hots[2*N];
array<int,2> edges[16*N];
int edges_idx=0;
int edges_start[4*N];
array<int,2> prv[N+1];
array<int,4> events[5*N];
int events_idx=0;
int cc_id[4*N];
int d[4*N];
int tmp[N];
int que[4*N];
int qid=0;
int qsz=0;
void ini_queue(){qid=qsz=0;}
void push_queue(int a){que[qsz++]=a;}
int front_queue()
{
if(qid<qsz) return que[qid++];
else return -1;
}
void update(int idx,int l,int r,int ql,int qr,int x)
{
if(ql>qr) return;
if(l==ql&&r==qr) tree[idx]=x;
else
{
int m=(l+r)/2;
update(2*idx,l,m,ql,min(qr,m),x);
update(2*idx+1,m+1,r,max(ql,m+1),qr,x);
}
}
int query(int idx,int l,int r,int pos)
{
if(l==r) return tree[idx];
int m=(l+r)/2;
if(pos<=m) return max(tree[idx],query(2*idx,l,m,pos));
else return max(tree[idx],query(2*idx+1,m+1,r,pos));
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//set up points
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
auto &[x,y]=points[i];
cin >> x >> y;
}
//x_compress
for(int i=1;i<=n;i++) que[i]=i;
sort(que+1,que+n+1,[&](int a,int b){return (points[a][0]<points[b][0]);});
int hx=0;
for(int i=1;i<=n;i++)
{
if(i>1&&points[que[i-1]][0]!=points[que[i]][0]) hx++;
tmp[que[i]]=hx;
}
for(int i=1;i<=n;i++) points[i][0]=tmp[i];
//y_compress
sort(que+1,que+n+1,[&](int a,int b){return (points[a][1]<points[b][1]);});
int hy=0;
for(int i=1;i<=n;i++)
{
if(i>1&&points[que[i-1]][1]!=points[que[i]][1]) hy++;
tmp[que[i]]=hy;
}
for(int i=1;i<=n;i++) points[i][1]=tmp[i];
//set up hots
int hot_cnt=0;
auto add_hot=[&](int x,int y)->int
{
hot_cnt++;
hot_pos[hot_cnt]={x,y,hot_cnt};
return hot_cnt;
};
for(int i=1;i<=n;i++)
{
auto &[x,y]=points[i];
for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) add_hot(x+j,y+k);
}
//set up walls
int m;
cin >> m;
for(int i=1;i<=m;i++)
{
auto &[a,b]=walls[i];
cin >> a >> b;
if(points[a]>points[b]) swap(a,b);
if(points[a][0]==points[b][0]) wall_hots[i]={4*(a-1)+2,4*(a-1)+4};
else wall_hots[i]={4*(a-1)+3,4*(a-1)+4};
}
//set up hots' edges
auto add_edge=[&](int a,int b)
{
edges[edges_idx++]={a,b};
edges[edges_idx++]={b,a};
};
auto process=[&]()
{
//extract edges
fill(tree,tree+4*(N+5),-1);
for(int i=0;i<=N;i++) prv[i]={-1,-1}; //x,hot_id
events_idx=0; //x,tp,[y,hot_id] or [yl,yr]
for(int i=1;i<=hot_cnt;i++) events[events_idx++]={hot_pos[i][0],0,hot_pos[i][1],i};
for(int i=1;i<=m;i++)
{
auto [a,b]=walls[i];
auto [xa,ya]=points[a];
auto [xb,yb]=points[b];
if(xa==xb) events[events_idx++]={xa,1,ya+1,yb};
}
sort(events,events+events_idx);
for(int i=0;i<events_idx;i++)
{
auto [x,tp,yl,yr]=events[i];
if(tp==0)
{
int w=query(1,0,N,yl);
auto [px,pid]=prv[yl];
if(w<px) add_edge(yr,pid);
prv[yl]={x,yr};
}
else update(1,0,N,yl,yr,x);
}
//flip coordinates
for(int i=1;i<=n;i++) swap(points[i][0],points[i][1]);
for(int i=1;i<=hot_cnt;i++) swap(hot_pos[i][0],hot_pos[i][1]);
};
process();
process();
int cc_cnt=0;
ini_queue();
sort(edges,edges+edges_idx);
for(int i=edges_idx-1;i>=0;i--) edges_start[edges[i][0]]=i;
//find hots' components
for(int i=1;i<=hot_cnt;i++)
{
if(cc_id[i]!=0) continue;
cc_cnt++;
auto add=[&](int a)
{
if(cc_id[a]==0)
{
cc_id[a]=cc_cnt;
push_queue(a);
}
};
add(i);
while(1)
{
int a=front_queue();
if(a==-1) break;
for(int j=edges_start[a];j<edges_idx&&edges[j][0]==a;j++) add(edges[j][1]);
}
}
//set up cc's edges
edges_idx=0;
for(int i=1;i<=m;i++)
{
auto [a,b]=wall_hots[i];
edges[edges_idx++]={cc_id[a],cc_id[b]};
edges[edges_idx++]={cc_id[b],cc_id[a]};
}
sort(edges,edges+edges_idx);
for(int i=edges_idx-1;i>=0;i--) edges_start[edges[i][0]]=i;
sort(hot_pos+1,hot_pos+hot_cnt+1);
ini_queue();
auto add=[&](int a,int nd)
{
if(d[a]==0)
{
d[a]=nd;
push_queue(a);
}
};
for(int i=1;i<=hot_cnt;i++)
{
auto [x,y,hot]=hot_pos[i];
add(cc_id[hot],1);
while(1)
{
int a=front_queue();
if(a==-1) break;
for(int j=edges_start[a];j<edges_idx&&edges[j][0]==a;j++) add(edges[j][1],d[a]+1);
}
}
vector<int> res;
for(int i=1;i<=m;i++)
{
auto [a,b]=wall_hots[i];
if(d[cc_id[a]]==d[cc_id[b]]) res.push_back(i);
}
cout << res.size() << "\n";
for(int w:res) cout << w << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2772 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2812 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
102 ms |
9284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
318 ms |
25700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
354 ms |
27020 KB |
Output is correct |
| 2 |
Runtime error |
532 ms |
33516 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
528 ms |
32604 KB |
Output is correct |
| 2 |
Correct |
494 ms |
31556 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
529 ms |
33508 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
