Submission #1268076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268076		coderg	Flood (IOI07_flood)	C++20	10 / 100	44 ms	9356 KiB

flood

#include<bits/stdc++.h>
using namespace std;

// mapa para comprimir coordenadas
map<int,int>mpx,mpy;
// arrays para almacenar coordenadas comprimidas
int X[200100],Y[200100],CCx,CCy;
// matriz para regiones (flood fill) y matriz de muros
int reg[550][550],wal[550][550][2];
// variables para regiones, visitados y muros caídos
int lev,R,vis[200100],fall[200100];
//  para almacenar paredes horizontales y verticales
vector<pair<int,int>> Wx,Wy;
//  grafo de regiones
vector<pair<int,int>> adj[200100];

//flood fill para identificar regiones conectadas
void flod(int x,int y,int c){
    // si está fuera de límites o ya tiene región, retorna
    if(x<0||y<0||x>CCx+2||y>CCy+2) return;
    if(reg[x][y]) return;
    
    // asigna la región actual a esta celda
    reg[x][y]=c;
    
    // propaga el flood fill en las 4 direcciones si no hay muro
    if(!wal[x][y][0])        // sin muro horizontal abajo
        flod(x,y-1,c);
    if(!wal[x][y+1][0])      // sin muro horizontal arriba
        flod(x,y+1,c);
    if(!wal[x][y][1])        // sin muro vertical a la izquierda
        flod(x-1,y,c);
    if(!wal[x+1][y][1])      // sin muro vertical a la derecha
        flod(x+1,y,c);
}

//  para añadir aristas al grafo
void AE(int a,int b,int c){
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,w;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>X[i]>>Y[i];
        mpx[X[i]];  // insertar en mapa para compresión
        mpy[Y[i]];
    }
    
    //comprimir coordenadas X
    for(auto&[i,j]:mpx)
        j=++CCx;
    // comprimir coordenadas Y
    for(auto&[i,j]:mpy)
        j=++CCy;
    
    // convertir coordenadas originales a comprimidas
    for(int i=1;i<=n;i++)
        X[i]=mpx[X[i]],
        Y[i]=mpy[Y[i]];
    
    cin>>w;//muros
    for(int i=1;i<=w;i++){
        int a,b;cin>>a>>b;
        
        // procesar muro vertical (misma coordenada X)
        if(X[a]==X[b]){
            if(Y[a]>Y[b])
                swap(a,b);
            // marcar muros verticales en la matriz
            for(int j=Y[a];j<Y[b];j++)
                wal[X[a]][j][1]=i;
            Wx.push_back({X[a],Y[a]});
        } 
        // procesar muro horizontal (misma coordenada Y)
        else {
            if(X[a]>X[b])swap(a,b);
            // marcar muros horizontales en la matriz
            for(int j=X[a];j<X[b];j++)
                wal[j][Y[b]][0]=i;
            Wy.push_back({X[a],Y[a]});
        }
    }
    
    //  flood fill para identificar regiones
    for(int i=0;i<CCx+2;i++)
        for(int j=0;j<CCy+2;j++)
            if(!reg[i][j])
                flod(i,j,++R);
    
    // construir grafo donde nodos son regiones y aristas son muros
    for(auto [i,j]:Wx)  // para muros verticales
        AE(reg[i-1][j],reg[i][j],wal[i][j][1]);
    for(auto [i,j]:Wy)  // para muros horizontales
        AE(reg[i][j-1],reg[i][j],wal[i][j][0]);
    
    // BFS desde la región exterior (región 1) para encontrar muros que caen
    queue<int>Q;
    Q.push(1);
    while(Q.size()){
        int x=Q.front();
        Q.pop();
        // explorar regiones adyacentes
        for(auto[i,j]:adj[x])
            if(!vis[i])
                Q.push(i),
                fall[j]=1;  // marcar muro como caído
        // marcar regiones como visitadas
        for(auto[i,j]:adj[x])
            vis[i]=1;
    }
    
    // recopilar muros que NO cayeron
    vector<int>v;
    for(int i=1;i<=w;i++) if(!fall[i])v.push_back(i);
    
    cout<<v.size()<<'\n';
    for(auto i:v)cout<<i<<'\n';
        
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9