#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 400005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
struct edge { int num; bool type; };
vector <edge> adj[400005];
struct point { int x,y; } a[100005];
pair <int,int> e[200005];
int n,m,i,u,v,nangle,f[N],mx[100005],ok,alone[100005];
bool visited[100005];
vector <int> angle_to_side[200005][2],res;
int main()
{
// freopen("flood.inp","r",stdin);
//freopen("flood.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
cin>>m;
for(i=1;i<=m;i++)
{
cin>>u>>v;
if(a[u].x>a[v].x || (a[u].x==a[v].x && a[u].y>a[v].y)) swap(u,v);
e[i]={ u,v };
adj[u].push_back({ v,0 });
adj[v].push_back({ u,0 });
}
auto BFS_point=[&](int u)
{
queue <int> q;
vector <int> node;
int ma=0;
q.push(u); visited[u]=1;
while(q.size()>0)
{
int u=q.front(); q.pop();
ma=max(ma,a[u].x);
node.push_back(u);
for(edge x:adj[u])
if(visited[x.num]==0) q.push(x.num),visited[x.num]=1;
}
for(int u:node) mx[u]=ma;
};
for(u=1;u<=n;u++)
if(visited[u]==0) BFS_point(u);
for(u=1;u<=n;u++) adj[u].clear();
for(i=1;i<=m;i++)
{
int u=e[i].fst,v=e[i].snd;
if(a[v].x>a[u].x) adj[u].push_back({ i,0 }),adj[v].push_back({ i,0 });
if(a[v].y>a[u].y) adj[u].push_back({ i,0 }),adj[v].push_back({ i,0 });
}
for(u=1;u<=n;u++)
{
vector <II> vec;
for(edge x:adj[u])
{
int v=(e[x.num].fst==u ? e[x.num].snd : e[x.num].fst),k;
if(a[u].y<a[v].y) k=1;
if(a[u].x<a[v].x) k=2;
if(a[u].y>a[v].y) k=3;
if(a[u].x>a[v].x) k=4;
vec.push_back({ x.num,k });
}
sort(vec.begin(),vec.end(),[&](II a,II b){ return a.snd<b.snd; });
if(vec.size()==0) continue;
else if(vec.size()==1)
{
II x=vec.back();
alone[u]=++nangle;
for(i=0;i<=1;i++)
angle_to_side[x.fst][i].push_back(nangle);
}
else
{
auto consider=[&](II a,II b)
{
int oka=(a.snd==1 || a.snd==4),okb=(b.snd==2 || b.snd==3);
nangle++;
angle_to_side[a.fst][oka].push_back(nangle);
angle_to_side[b.fst][okb].push_back(nangle);
};
for(i=1;i<vec.size();i++)
consider(vec[i-1],vec[i]);
consider(vec.back(),vec[0]);
}
}
for(u=1;u<=n;u++) adj[u].clear();
for(i=1;i<=m;i++)
{
for(ok=0;ok<=1;ok++)
{
u=angle_to_side[i][ok][0],v=angle_to_side[i][ok][1];
adj[u].push_back({ v,0 }),adj[v].push_back({ u,0 });
}
u=angle_to_side[i][0][0],v=angle_to_side[i][1][0];
adj[u].push_back({ v,1 }),adj[v].push_back({ u,1 });
}
memset(f,63,sizeof(f));
set <pair <int,int> > s;
for(i=1;i<=m;i++)
{
int u=e[i].fst,v=e[i].snd;
if(a[v].x==mx[v])
{
if(a[u].x==a[v].x)
for(int u:angle_to_side[i][1])
s.insert({ 0,u }),f[u]=0;
else if(alone[v]>0)
s.insert({ 0,alone[v] }),f[alone[v]]=0;
}
}
while(s.size()>0)
{
int u=s.begin()->snd; s.erase(s.begin());
for(edge x:adj[u])
{
int v=x.num,k=x.type;
if(f[v]>f[u]+k)
{
s.erase({ f[v],v });
f[v]=f[u]+k;
s.insert({ f[v],v });
}
}
}
for(i=1;i<=m;i++)
{
int u=angle_to_side[i][0][0],v=angle_to_side[i][1][0];
if(f[u]==f[v]) res.push_back(i);
}
cout<<res.size()<<'\n';
for(int x:res) cout<<x<<'\n';
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(i=1;i<vec.size();i++)
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
5 ms |
24036 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
5 ms |
24312 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
5 ms |
24036 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
23900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
24128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
6 ms |
24156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
6 ms |
24032 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
28252 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
100 ms |
40484 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
110 ms |
42196 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
266 ms |
46456 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
320 ms |
49148 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
