| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1268081 | coderg | Flood (IOI07_flood) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
// para 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];
void AE(int a, int b, int c) {
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
int main() {
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;
}