#include <bits/stdc++.h>
#define NMAX 200001
//#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF 1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*-------------Initialize------------*/
struct nod{
int x, y;
}node[NMAX];
struct edge{
int node,up,right,down,left;
};
vector<vector<edge>>G(NMAX);
vector<pii>edges;
bool alive[NMAX];
int n,w,max_x,max_y;
int di[]={0,0,1,-1};
int dj[]={1,-1,0,0};
int mat[1010][1010];
int tim[1010][1010];
/*-------positions of wall a->b--------- */
edge wall_pos(int a,int b)
{
int left=min(node[a].x,node[b].x);
int right=max(node[a].x,node[b].x);
int up=min(node[a].y,node[b].y);
int down=max(node[a].y,node[b].y);
return{b,up,right,down,left};
}
/*-----Subtask1(x,y<=500)-------*/
void subtask1()
{
for(int i=1;i<=n;++i)
{
mat[node[i].x][node[i].y]=i;
}
auto draw_edge=[&](int x,int y){
int imin=min(node[x].x,node[y].x);
int imax=max(node[x].x,node[y].x);
int jmin=min(node[x].y,node[y].y);
int jmax=max(node[x].y,node[y].y);
for(int i=imin;i<=imax;++i)
{
for (int j=jmin;j<=jmax;++j)
{
if(!mat[i][j])
mat[i][j]=-1;
}
}
};
for(auto [x,y]:edges)
{
draw_edge(x,y);
}
auto inmat=[&](int i,int j)
{
return i>=0 && i<=1001 && j>=0 && j<=1001;
};
deque<pii>dq;
dq.push_front({0,0});
tim[0][0]=1;
while(!dq.empty())
{
auto [x,y]=dq.front();
// cout<<x<<" "<<y<<nl;
dq.pop_front();
for(int d=0;d<4;++d)
{
int inou=x+di[d];
int jnou=y+dj[d];
if(inmat(inou,jnou) && !tim[inou][jnou])
{
int weight=0;
if(mat[inou][jnou]!=0)
weight=1;
tim[inou][jnou]=tim[x][y]+weight;
if(weight)
dq.push_back({inou,jnou});
else
dq.push_front({inou,jnou});
}
}
}
int ans=w;
auto alive_=[&](int x,int y,int ind){
int imin=min(node[x].x,node[y].x);
int imax=max(node[x].x,node[y].x);
int jmin=min(node[x].y,node[y].y);
int jmax=max(node[x].y,node[y].y);
bool ok=true;
if(imin==imax)
{
for(int j=jmin+1;j<jmax;++j)
{
if(tim[imin-1][j]!=tim[imin+1][j])
ok=false;
}
}
else
{
for(int i=imin+1;i<imax;++i)
{
if(tim[i][jmin-1]!=tim[i][jmin+1])
ok=false;
}
}
if(!ok)
ans--;
alive[ind]=ok;
};
for(int i=1;i<=w;++i)
{
auto [x,y]=edges[i-1];
alive_(x,y,i);
}
cout<<ans<<nl;
for(int i=1;i<=w;++i)
{
if(alive[i])
cout<<i<<nl;
}
// for(int i=0;i<=20;++i)
// {
// for(int j=0;j<=20;++j)
// {
// cout<<tim[i][j]<<" ";
// }
// cout<<nl;
// }
return;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i=1;i<=n;++i)
{
int x,y;
cin>>x>>y;
swap(x,y);
max_x=max(max_x,2*x);
max_y=max(max_y,2*y);
node[i]={2*x,2*y};
}
cin>>w;
for(int i=1;i<=w;++i)
{
int x,y;
cin>>x>>y;
edges.pb({x,y});
G[x].pb(wall_pos(x,y));
alive[i]=true;
}
if(max_x<=2000 && max_y<=2000)
{
subtask1();
}
else if(n<=500)
{
cout<<0;
}
return 0;
}
Compilation message
flood.cpp:9: warning: "LLONG_MAX" redefined
9 | #define LLONG_MAX 9223372036854775807
|
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
from /usr/include/c++/10/climits:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
from flood.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
135 | # define LLONG_MAX __LONG_LONG_MAX__
|
flood.cpp: In function 'void subtask1()':
flood.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for(auto [x,y]:edges)
| ^
flood.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | auto [x,y]=dq.front();
| ^
flood.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
129 | auto [x,y]=edges[i-1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
12 ms |
16208 KB |
Output is correct |
| 3 |
Correct |
13 ms |
16476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
16220 KB |
Output is correct |
| 2 |
Correct |
12 ms |
16952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7892 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
10436 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
10764 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
11964 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
13508 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
