Submission #1268085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268085		coderg	Flood (IOI07_flood)	C++20	73 / 100	49 ms	16968 KiB

flood

#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

// arrays para almacenar coordenadas y estados
int x[100100], y[100100];           // coordenadas de los puntos
int lev[200005];                    // niveles para bfs 0-1
int side[100100][4][2];             // almacena información de lados/muros
int vec[200005];                    // coordenada x asociada a un muro
bitset<200005> vis;                 // array de visitados 
vector<int> adj[200005];            // lista de adyacencia

void ae(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
}

// conjunto para procesar muros ordenados por coordenada x
set<pair<int, int>> st;

int main() {
    fastIO;
    int n, w;cin>>n;
    for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];
    cin >> w;
    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);
            
            // asignar identificadores de muro a los lados de los puntos
            // lado 2 = inferior, lado 0 = superior
            side[a][2][1] = i;          // lado inferior del punto a
            side[a][2][0] = i+w;      // extremo virtual opuesto
            side[b][0][0] = i;          // lado superior del punto b  
            side[b][0][1] = i+w;      // extremo virtual opuesto
            
            vec[i] = x[a];              // almacenar coordenada x del muro
            st.insert({vec[i], i});     // insertar en conjunto ordenado
            
        } 
        // procesar muro horizontal (misma coordenada y)
        else {
            if (x[a] > x[b]) swap(a, b);
            
            // asignar identificadores de muro a los lados de los puntos
            // lado 1 = derecho, lado 3 = izquierdo
            side[a][1][0] = i;          // lado derecho del punto a
            side[a][1][1] = i + w;      // extremo virtual opuesto
            side[b][3][1] = i;          // lado izquierdo del punto b
            side[b][3][0] = i + w;      // extremo virtual opuesto
            
            vec[i] = 1e9;               // valor alto para muros horizontales
        }
    }
    
    // conectar muros adyacentes alrededor de cada punto
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 4; j++) {
            if (side[i][j][1]) {        // si hay un muro en este lado
                // buscar el siguiente muro en sentido horario
                for (int k = (j + 1) % 4; ; k = (k + 1) % 4) {
                    if (side[i][k][0]) {  // si encontramos otro muro
                        // conectar los extremos de los muros (misma región)
                        ae(side[i][k][0], side[i][j][1]);
                        break;
                    }
                }
            }
        }
    }
    
    // bfs 0-1 para encontrar el camino más corto desde el exterior
    deque<int> q;
    memset(lev, 7, sizeof lev);  // inicializar con valor grande
    
    while (true) {
        if (st.empty()) break;
        
        // tomar el muro vertical más a la izquierda (exterior)
        int k = st.begin()->second;
        q.push_back(k);
        lev[k] = 0;
        
        while (q.size()) {
            int x = q.front(); 
            q.pop_front();
            
            if (vis[x]) continue;
            if (x <= w) st.erase({vec[x], x});  // eliminar del conjunto si es muro real
            
            vis[x] = 1;
            
            // explorar conexiones de mismo peso (peso 0)
            for (auto y : adj[x]) {
                if (lev[y] > lev[x]) {
                    q.push_front(y);
                    lev[y] = lev[x];
                }
            }
            adj[x].clear();  // limpiar lista de adyacencia para eficiencia
            
            // explorar conexión al extremo opuesto del muro (peso 1)
            int k = (x > w ? x - w : x + w);
            if (lev[k] > lev[x] + 1) {
                lev[k] = lev[x] + 1;
                q.push_back(k);
            }
        }
    }
    
    //encontrar muros que permanecen (mismo nivel en ambos extremos)
    vector<int> v;
    for (int i = 1; i <= w; i++)
        if (lev[i] == lev[i + w])
            v.push_back(i);
    
    cout << v.size() << '\n';
    for (auto i : v)cout<<i<<'\n';
        
    return 0;
}

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