#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=100005,M=502;
const int xx[4]={-1,1,0,0};
const int yy[4]={0,0,-1,1};
struct ban
{
int x,y;
};
int n,m;
ban a[N],b[N];
int u[M][M];
int k;
int c[M][M];
void dfs(int x,int y)
{
c[x][y]=k;
for(int i=0;i<4;++i)
{
if(!(u[x][y]&(1<<i)))
continue;
int hx=x+xx[i];
int hy=y+yy[i];
if(hx>=0 && hx<M && hy>=0 && hy<M && !c[hx][hy])
dfs(hx,hy);
}
}
vector<int> g[N];
int d[N];
void bfs()
{
queue<int> q;
d[1]=1;
q.push(1);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<g[x].size();++i)
{
int h=g[x][i];
if(!d[h])
{
d[h]=d[x]+1;
q.push(h);
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
map<int,int> mpx,mpy;
vector<int> vx,vy;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>a[i].x>>a[i].y;
vx.push_back(a[i].x);
vy.push_back(a[i].y);
}
sort(vx.begin(),vx.end());
int z=1;
for(int i=0;i<vx.size();++i)
{
if(!i || vx[i]!=vx[i-1])
mpx[vx[i]]=z++;
}
sort(vy.begin(),vy.end());
z=1;
for(int i=0;i<vy.size();++i)
{
if(!i || vy[i]!=vy[i-1])
mpy[vy[i]]=z++;
}
for(int i=0;i<n;++i)
{
a[i].x=mpx[a[i].x];
a[i].y=mpy[a[i].y];
}
cin>>m;
for(int i=0;i<m;++i)
{
cin>>b[i].x>>b[i].y;
--b[i].x;
--b[i].y;
}
///////////////////////////////////
for(int x=0;x<M;++x)
{
for(int y=0;y<M;++y)
{
u[x][y]=(1<<4)-1;
}
}
for(int k=0;k<m;++k)
{
int i=b[k].x;
int j=b[k].y;
if(a[i].x==a[j].x)
{
for(int y=min(a[i].y,a[j].y);y<max(a[i].y,a[j].y);++y)
{
u[a[i].x][y]=(u[a[i].x][y])^(1<<0);
u[a[i].x-1][y]=(u[a[i].x-1][y])^(1<<1);
}
}
else
{
for(int x=min(a[i].x,a[j].x);x<max(a[i].x,a[j].x);++x)
{
u[x][a[i].y]=(u[x][a[i].y])^(1<<2);
u[x][a[i].y-1]=(u[x][a[i].y-1])^(1<<3);
}
}
}
for(int x=0;x<M;++x)
{
for(int y=0;y<M;++y)
{
if(!c[x][y])
{
++k;
dfs(x,y);
}
}
}
for(int k=0;k<m;++k)
{
int i=b[k].x;
int j=b[k].y;
if(a[i].x==a[j].x)
{
int y=min(a[i].y,a[j].y);
g[c[a[i].x][y]].push_back(c[a[i].x-1][y]);
g[c[a[i].x-1][y]].push_back(c[a[i].x][y]);
}
else
{
int x=min(a[i].x,a[j].x);
g[c[x][a[i].y]].push_back(c[x][a[i].y-1]);
g[c[x][a[i].y-1]].push_back(c[x][a[i].y]);
}
}
bfs();
vector<int> ans;
for(int k=0;k<m;++k)
{
int i=b[k].x;
int j=b[k].y;
if(a[i].x==a[j].x)
{
int y=min(a[i].y,a[j].y);
if(d[c[a[i].x][y]]==d[c[a[i].x-1][y]])
ans.push_back(k+1);
}
else
{
int x=min(a[i].x,a[j].x);
if(d[c[x][a[i].y]]==d[c[x][a[i].y-1]])
ans.push_back(k+1);
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();++i)
cout<<ans[i]<<endl;
return 0;
}
Compilation message
flood.cpp: In function 'void bfs()':
flood.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();++i)
~^~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vx.size();++i)
~^~~~~~~~~~
flood.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vy.size();++i)
~^~~~~~~~~~
flood.cpp:172:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ans.size();++i)
~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
16504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
16504 KB |
Output is correct |
| 2 |
Correct |
33 ms |
16504 KB |
Output is correct |
| 3 |
Correct |
28 ms |
16564 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
16376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
15752 KB |
Output is correct |
| 2 |
Correct |
28 ms |
16424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
26 ms |
16380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
16436 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
15224 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
14580 KB |
Output is correct |
| 2 |
Correct |
27 ms |
15864 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
13944 KB |
Output is correct |
| 2 |
Correct |
28 ms |
16376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
112 ms |
12892 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
230 ms |
18012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
252 ms |
22608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
281 ms |
15792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
287 ms |
15724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
