제출 #1268083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268083		coderg	Flood (IOI07_flood)	C++20	73 / 100	198 ms	35352 KiB

flood

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

//  almacenar coordenadas y estados
int X[100100], Y[100100];           //coordenadas de los puntos
int vis[400100], lev[400100];       // visitados y niveles para BFS 0-1
int side[100100][4][2];             // almacena información de lados/muros
int Xof[400100];                    // coordenada X asociada a un muro

// grafo (nodo, peso)
vector<pair<int, bool>> adj[400100];

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

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

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
            side[a][2][1] = i;          // lado inferior del punto a
            side[a][2][0] = i + w;      // "virtual" para el otro extremo
            side[b][0][0] = i;          // lado superior del punto b  
            side[b][0][1] = i + w;      // "virtual" para el otro extremo
            
            Xof[i] = X[a];              // almacenar coordenada X del muro
            st.insert({Xof[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
            side[a][1][0] = i;          // lado derecho del punto a
            side[a][1][1] = i + w;      // "virtual" para el otro extremo
            side[b][3][1] = i;          // lado izquierdo del punto b
            side[b][3][0] = i + w;      // "virtual" para el otro extremo
            Xof[i] = 1e9;               // valor alto para muros horizontales
        }
        
        // conectar los dos extremos del muro con peso 1
        AE(i, i+w, 1);
    }
    
    // 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 muros con peso 0 (misma región)
                        AE(side[i][k][0], side[i][j][1], 0);
                        break;
                    }
                }
            }
        }
    }
    
    // BFS 0-1 para encontrar el camino más corto desde el exterior
    deque<int> Q;
    memset(lev, 7, sizeof lev); 
    
    while (true) {
        if (st.empty()) break;
        // tomar el muro vertical más a la izquierda
        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({Xof[x], x});  // eliminar del conjunto si es muro real
            vis[x] = 1;
            
            // explorar vecinos
            for (auto [i, j] : adj[x]) {
                if (lev[i] > lev[x] + j) {
                    if (j) {
                        // peso 1: ir al final de la cola
                        Q.push_back(i);
                        lev[i] = lev[x] + 1;
                    } else {
                        // peso 0: ir al frente de la cola
                        Q.push_front(i);
                        lev[i] = lev[x];
                    }
                }
            }
            adj[x].clear();  
        }
    }
    
    // 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