| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314947 | exoworldgd | Flood (IOI07_flood) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
#define pii pair<int,int>
using namespace std;
const int inf=LLONG_MAX,mod=1e9+7,N=1e5+5,dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int n,m,cnt=0,R;
struct pt{
int x,y,c,r[4];
pii l[4];
pt(){c=-1,l[0]=l[1]=l[2]=l[3]={-1,-1},fill(r,r+4,-1);}
};
vector<pt>pts;
struct reg{
int t,a;
vector<int> v;
reg(){a=0,t=-1;}
};
int d(int x,int y){return pts[x].y==pts[y].y?(pts[x].x<pts[y].x?0:2):(pts[x].y>pts[y].y?1:3);}
void bfs(int x, int k) {
queue<int> q;
pts[x].c=k;
for(q.push(x);q.size();q.pop()) {
x=q.front();
for(int i=0;i<4;i++)if(pts[x].l[i].first^-1&&pts[pts[x].l[i].first].c==-1)pts[pts[x].l[i].first].c=k,q.push(pts[x].l[i].first);
}
}
void tv(int i,int j,reg &rg,int id) {
rg.v.push_back(i);
for(int k;pts[i].r[j]==-1;){
pts[i].r[j]=id,k=pts[i].l[j].first,rg.a+=(pts[i].x-pts[k].x)*pts[i].y,rg.v.push_back(k),i=k;
for(j=(j+3)%4;pts[i].l[j].first==-1;j=(j+1)%4);
}
rg.a=max(rg.a,-rg.a);
}
signed main(void) {
exoworldgd;
cin>>n;
pt t;
for(int i=0;i<n;i++)cin>>t.x>>t.y,pts.push_back(t);
cin>>m;
for(int i=0,a,b;i<m;i++)cin>>a>>b,a--,b--,pts[a].l[d(a,b)]={b,i},pts[b].l[d(b,a)]={a,i};
for(int i=0;i<n;i++)if(pts[i].c==-1)bfs(i,cnt++);
vector<int> exr(cnt,-1),res;
vector<reg> regs;
for(int i=0;i<n;i++)for(int j=0;j<4;j++)if(pts[i].l[j].first^-1&&pts[i].r[j]==-1) {
R=regs.size(),regs.push_back(reg()), tv(i,j,regs[R],R);
int &ex=exr[pts[i].c];
if(ex==-1)ex=R;
if(regs[R].a>regs[ex].a)ex=R;
}
queue<int> q;
for(int i=0;i<cnt;i++)if(exr[i]^-1)regs[exr[i]].t=0,q.push(exr[i]);
for(;q.size();q.pop()){
int x=q.front();
for(int i=1;i<regs[x].v.size();i++){
int a=regs[x].v[i],b=regs[x].v[i-1], s=pts[a].r[d(a,b)];
if(regs[s].t==-1)regs[s].t=regs[x].t+1,q.push(s);
}
}
for(int a=0;a<n;a++)for(int i=0;i<4;i++) {
int b=pts[a].l[i].first;
if(!(b==-1||b<a)&®s[pts[a].r[d(a,b)]].t==regs[pts[b].r[d(b,a)]].t)res.push_back(pts[a].l[i].second);
}
cout<<res.size()<<'\n';
for(int i:res)cout<<i+1<<'\n';
}