กำแพงกับน้ำท่วม: ประโยคว่าพังทีละชั่วโมง แปลเป็นระยะทางบนกราฟได้ตรง ๆ

// เฉลยชุดทดสอบย่อย (พิกัดไม่เกิน 500 หรือจุดไม่เกิน 500) มองพื้นที่เป็นตารางช่องละหนึ่งหน่วย
#include <bits/stdc++.h>
using namespace std;
int G;
static inline int cid(int i,int j){ return i*G+j; }
// แทนพิกัดด้วยลำดับที่ของมันในพิกัดที่ไม่ซ้ำกัน เริ่มจาก 1 เพื่อเหลือวงช่องรอบนอกไว้เป็นทะเล
// ลำดับซ้ายขวาบนล่างของทุกจุดเหมือนเดิม รูปผังจึงเหมือนเดิม แค่ถูกบีบให้แน่นขึ้น
int squeeze(vector<int>& v){
    vector<int> s(v.begin()+1,v.end());
    sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end());
    for(size_t i=1;i<v.size();i++) v[i]=int(lower_bound(s.begin(),s.end(),v[i])-s.begin())+1;
    return (int)s.size();
}
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> X(n+1),Y(n+1);
    for(int i=1;i<=n;i++) scanf("%d %d",&X[i],&Y[i]);
    int w; scanf("%d",&w);
    vector<int> A(w+1),B(w+1);
    for(int i=1;i<=w;i++) scanf("%d %d",&A[i],&B[i]);
    G=max(squeeze(X),squeeze(Y))+2;
    vector<char> blkH((size_t)G*G,0), blkV((size_t)G*G,0);   // blkH[i][j] = กำแพงระหว่างช่อง (i,j-1) กับ (i,j)
    for(int e=1;e<=w;e++){
        int a=A[e],b=B[e];
        if(Y[a]==Y[b]){ int yy=Y[a],x1=min(X[a],X[b]),x2=max(X[a],X[b]);
            for(int i=x1;i<x2;i++) blkH[cid(i,yy)]=1; }
        else { int xx=X[a],y1=min(Y[a],Y[b]),y2=max(Y[a],Y[b]);
            for(int j=y1;j<y2;j++) blkV[cid(xx,j)]=1; }
    }
    // BFS แบบ 0-1: ข้ามขอบว่างราคา 0 ใส่หน้าคิว ข้ามกำแพงราคา 1 ต่อท้ายคิว
    const int INF=INT_MAX;
    vector<int> dist((size_t)G*G,INF);
    deque<int> dq; dist[cid(0,0)]=0; dq.push_back(cid(0,0));
    while(!dq.empty()){
        int u=dq.front(); dq.pop_front();
        int i=u/G,j=u%G,d=dist[u];
        auto go=[&](int ni,int nj,int cost){
            if(ni<0||nj<0||ni>=G||nj>=G) return;
            int v=cid(ni,nj); if(d+cost<dist[v]){ dist[v]=d+cost; if(cost) dq.push_back(v); else dq.push_front(v); }
        };
        go(i,j+1, blkH[cid(i,j+1)]);
        go(i,j-1, blkH[cid(i,j)]);
        go(i+1,j, blkV[cid(i+1,j)]);
        go(i-1,j, blkV[cid(i,j)]);
    }
    // กำแพงรอดเมื่อช่องสองข้างของมันถูกน้ำถึงในชั่วโมงเดียวกัน
    vector<int> ans;
    for(int e=1;e<=w;e++){
        int a=A[e],b=B[e]; bool alive;
        if(Y[a]==Y[b]){ int yy=Y[a],x1=min(X[a],X[b]); alive = dist[cid(x1,yy-1)]==dist[cid(x1,yy)]; }
        else { int xx=X[a],y1=min(Y[a],Y[b]); alive = dist[cid(xx-1,y1)]==dist[cid(xx,y1)]; }
        if(alive) ans.push_back(e);
    }
    printf("%d\n",(int)ans.size());
    for(int e:ans) printf("%d\n",e);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> X(n+1),Y(n+1);
    for(int i=1;i<=n;i++) scanf("%d %d",&X[i],&Y[i]);
    int w; scanf("%d",&w);
    // กำแพง e แตกเป็นครึ่งเส้นสองอัน 2e (a ไป b) กับ 2e+1 (b ไป a)
    // ทิศ 0=ตะวันออก 1=เหนือ 2=ตะวันตก 3=ใต้  ทิศย้อนกลับของ d คือ d^2
    vector<array<int,4>> out(n+1,{-1,-1,-1,-1});   // ครึ่งเส้นที่ออกจากจุดนี้ไปทางทิศนั้น
    vector<int> heTo(2*w),heDir(2*w);
    for(int e=0;e<w;e++){
        int a,b; scanf("%d %d",&a,&b);
        int d = (Y[a]==Y[b]) ? (X[b]>X[a] ? 0 : 2) : (Y[b]>Y[a] ? 1 : 3);
        heTo[2*e]=b;   heDir[2*e]=d;     out[a][d]=2*e;
        heTo[2*e+1]=a; heDir[2*e+1]=d^2; out[b][d^2]=2*e+1;
    }
    // เดินรอบแต่ละหน้า โดยให้หน้านั้นอยู่ทางซ้ายมือเสมอ
    // ถึงจุดปลายแล้ว ลองเลี้ยวซ้ายก่อน ไม่ได้ก็ตรงไป ไม่ได้ก็เลี้ยวขวา สุดท้ายค่อยย้อนกลับ
    vector<int> heFace(2*w,-1);
    vector<char> isRoom;                       // หน้านี้คือด้านในของห้อง (เดินทวนเข็ม) หรือไม่
    for(int s=0;s<2*w;s++){
        if(heFace[s]>=0) continue;
        int fid=(int)isRoom.size(); ll area2=0; int h=s;
        do{
            heFace[h]=fid;
            int u=heTo[h^1], v=heTo[h];
            area2 += (ll)X[u]*Y[v] - (ll)X[v]*Y[u];   // สูตรเชือกผูกรองเท้า ได้สองเท่าของพื้นที่ มีเครื่องหมาย
            int back=heDir[h]^2, nxt=-1;
            for(int k=3;k>=0;k--){ int dd=(back+k)%4; if(out[v][dd]>=0){ nxt=out[v][dd]; break; } }
            h=nxt;
        } while(h!=s);
        isRoom.push_back(area2>0);
    }
    // หน้าที่ไม่ใช่ห้อง คือขอบนอกของก้อนกำแพงแต่ละก้อน ยุบรวมเป็นปมเดียวคือทะเล (ปม 0)
    // ก้อนที่ลอยอยู่ในห้องก็ยุบเข้าทะเลได้ ชั่วโมงของทั้งก้อนจะเลื่อนลงเท่ากันหมด
    // ผลต่างสองข้างของกำแพงทุกเส้นจึงไม่เปลี่ยน
    int F=(int)isRoom.size();
    vector<int> node(F); int V=1;
    for(int f=0;f<F;f++) node[f] = isRoom[f] ? V++ : 0;
    // กราฟคู่: ปมคือหน้า เส้นเชื่อมคือกำแพง เก็บแบบอาร์เรย์ต่อกันเพื่อประหยัดหน่วยความจำ
    vector<int> deg(V+1,0), adj(2*w);
    for(int e=0;e<w;e++){ deg[node[heFace[2*e]]+1]++; deg[node[heFace[2*e+1]]+1]++; }
    for(int v=0;v<V;v++) deg[v+1]+=deg[v];
    vector<int> pos(deg.begin(),deg.end()-1);
    for(int e=0;e<w;e++){ int a=node[heFace[2*e]], b=node[heFace[2*e+1]]; adj[pos[a]++]=b; adj[pos[b]++]=a; }
    // BFS จากทะเล dist[v] คือชั่วโมงที่น้ำท่วมถึงหน้านั้น
    vector<int> dist(V,-1), q; q.reserve(V);
    dist[0]=0; q.push_back(0);
    for(size_t i=0;i<q.size();i++){
        int u=q[i];
        for(int k=deg[u];k<deg[u+1];k++){ int v=adj[k]; if(dist[v]<0){ dist[v]=dist[u]+1; q.push_back(v); } }
    }
    // กำแพงรอดเมื่อสองข้างถูกน้ำถึงในชั่วโมงเดียวกัน
    vector<int> ans;
    for(int e=0;e<w;e++) if(dist[node[heFace[2*e]]]==dist[node[heFace[2*e+1]]]) ans.push_back(e+1);
    printf("%d\n",(int)ans.size());
    for(int e:ans) printf("%d\n",e);
}

// ตัวตรวจ: ปล่อยน้ำตามโจทย์ทีละชั่วโมงจริง ๆ บนตาราง (พิกัดเล็กเท่านั้น)
// ไม่ใช้ข้อสรุปเรื่องชั่วโมงเท่ากันเลย ใช้แค่กติกาในโจทย์ตรง ๆ
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> X(n+1),Y(n+1); int mx=0;
    for(int i=1;i<=n;i++){ scanf("%d %d",&X[i],&Y[i]); X[i]++; Y[i]++; mx=max(mx,max(X[i],Y[i])); }
    int w; scanf("%d",&w);
    int G=mx+2;
    auto cid=[&](int i,int j){ return i*G+j; };
    // wh[i][j] = กำแพงที่คั่นช่อง (i,j-1) กับ (i,j)  wv[i][j] = กำแพงที่คั่นช่อง (i-1,j) กับ (i,j)  (-1 คือไม่มี)
    vector<int> wh(G*G,-1), wv(G*G,-1);
    for(int e=1;e<=w;e++){
        int a,b; scanf("%d %d",&a,&b);
        if(Y[a]==Y[b]){ for(int i=min(X[a],X[b]);i<max(X[a],X[b]);i++) wh[cid(i,Y[a])]=e; }
        else { for(int j=min(Y[a],Y[b]);j<max(Y[a],Y[b]);j++) wv[cid(X[a],j)]=e; }
    }
    vector<char> down(w+1,0);
    while(true){
        // น้ำไหลจากทะเลผ่านทุกขอบที่ไม่มีกำแพงยืนอยู่
        vector<char> wet(G*G,0); vector<int> st={cid(0,0)}; wet[cid(0,0)]=1;
        auto open=[&](int e){ return e<0 || down[e]; };
        while(!st.empty()){
            int u=st.back(); st.pop_back(); int i=u/G,j=u%G;
            auto go=[&](int ni,int nj,int e){ if(ni<0||nj<0||ni>=G||nj>=G) return; int v=cid(ni,nj); if(!wet[v]&&open(e)){ wet[v]=1; st.push_back(v);} };
            if(j+1<G) go(i,j+1,wh[cid(i,j+1)]);
            go(i,j-1,j>0?wh[cid(i,j)]:-1);
            if(i+1<G) go(i+1,j,wv[cid(i+1,j)]);
            go(i-1,j,i>0?wv[cid(i,j)]:-1);
        }
        // กำแพงที่ยังยืนและมีน้ำข้างเดียว พังพร้อมกันทั้งหมดในชั่วโมงนี้
        vector<int> fall;
        for(int i=0;i<G;i++) for(int j=0;j<G;j++){
            if(j>0){ int e=wh[cid(i,j)]; if(e>0&&!down[e]&&wet[cid(i,j-1)]!=wet[cid(i,j)]) fall.push_back(e); }
            if(i>0){ int e=wv[cid(i,j)]; if(e>0&&!down[e]&&wet[cid(i-1,j)]!=wet[cid(i,j)]) fall.push_back(e); }
        }
        if(fall.empty()) break;
        for(int e:fall) down[e]=1;
    }
    vector<int> ans; for(int e=1;e<=w;e++) if(!down[e]) ans.push_back(e);
    printf("%d\n",(int)ans.size());
    for(int e:ans) printf("%d\n",e);
}