Submission #435976

#	Time	Username	Problem	Language	Result	Execution time	Memory
435976		ocarima	Keys (IOI21_keys)	C++17	0 / 100	12 ms	14284 KiB

keys

#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b) cout << x[ii] << ", "; cout << "]" << nl

#define MAX_N 300002

#define destino first
#define tipo second

vector<pair<int, int> > hijos[MAX_N];
vector<int> nodosciclo[MAX_N];
int visitado[MAX_N], ciclo[MAX_N], minimo, origen, alcance;
vector<pair<int, int> > largociclo;
stack<int> s;
bool ciclodoble;

void dfs(int nodo){
    int h;
    visitado[nodo] = 1;
    s.push(nodo);
    for (auto hh : hijos[nodo]){
        h = hh.destino;
        if (visitado[h] == 0) dfs(h);
        else if (visitado[h] == 1){ // SE ENCONTRO UN CICLO
            while (s.top() != h){
                ciclo[s.top()] = h;
                nodosciclo[h].push_back(s.top());
                visitado[s.top()] = 2;
                s.pop();
            }
            nodosciclo[h].push_back(h);
            ciclo[h] = h;
            visitado[h] = 2;
            s.pop();

            largociclo.emplace_back(nodosciclo[h].size(), h);
        }
    }
    visitado[nodo] = 2;
    if (!s.empty() && s.top() == nodo) s.pop();
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 1);

    // CONSTRUYE UN GRAFO DIRIGIDO UNICAMENTE CON LAS ARISTAS QUE SE PUEDEN USAR CON LA LLAVE DE CADA CUARTO
    rep(i, 0, u.size() - 1){
        if (c[i] == r[u[i]]) hijos[u[i]].emplace_back(v[i], c[i]); // SI LA LLAVE EN EL CUARTO u PUEDE ABRIR ESA PUERTA, AGREGALA AL GRAFO DE u -> v
        if (c[i] == r[v[i]]) hijos[v[i]].emplace_back(u[i], c[i]); // SI LA LLAVE EN EL CUARTO v PUEDE ABRIR ESA PUERTA, AGREGALA AL GRAFO DE v -> u
    }

    // DENTRO DEL GRAFO DIRIGIDO ANTERIOR UNA HOJA REPRESENTA UN CUARTO QUE NO PUEDE LLEGAR A NINGUN OTRO Y POR LO TANTO SERIA MINIMO
    // SI NO HAY NINGUNA HOJA, ENTONCES BUSCAMOS CICLOS QUE NO BIFURQUEN, ES DECIR, QUE PUEDEN ENTRAR ARISTAS, PERO NO DEBE SALIR NINGUNA.
    // EL CUARTO CON ALCANCE MINIMO PERTENECE A ALGUNO DE ESTOS CICLOS.
    rep(cuarto, 0, r.size() - 1) ciclo[cuarto] = -1;
    rep(cuarto, 0, r.size() - 1) if (!visitado[cuarto]) dfs(cuarto);

    sort(largociclo.begin(), largociclo.end());
    minimo = r.size();

    // PARA CADA CICLO REVISA EL ALCANCE QUE TIENE
    for (auto c : largociclo){
        if (c.first > minimo) continue;
        origen = c.second;
        alcance = 0;

        vector<int> vis(r.size(), 0); // PERMITE SABER QUE NODOS YA FUERON VISITADOS
	    vector<int> llave(r.size(), 0); // PERMITE SABER QUE LLAVES YA SE TIENEN
	    vector<queue<int> > aristas (r.size()); // PERMITE GUARDAR LAS ARISTAS QUE SE ACTIVARAN SI SE ENCUENTRA UN TIPO DE LLAVE
	    queue<int> q;
	    ciclodoble = false;

	    vis[origen] = 1; // VISITA EL NODO ACTUAL
	    alcance = 1;
	    q.push(origen);
	    while (!q.empty()){
            int nodo = q.front();
            q.pop();
            for (auto h : hijos[nodo]){ // REVISA TODOS LOS NODOS A LOS QUE ESTA CONECTADO
                if (llave[h.tipo]){ // SI YA TIENE EL TIPO DE LLAVE NECESARIO
                    if (!vis[h.destino]){ // Y EL NODO NO HA SIDO VISITADO, ENTONCES VISITALO Y AGREGALO A LA COLA
                        if (ciclo[h.destino] != origen && ciclo[h.destino] != -1){ // SI PERTENECE A OTRO CICLO ENTONCES NO TIENE CASO SEGUIR VIENDO ESTE.
                           ciclodoble = true;
                           break;
                        }
                        vis[h.destino] = 1;
                        ++alcance;
                        q.push(h.destino);
                    }
                    // SI YA FUE VISITADO NO ES NECESARIO HACER NADA
                }
                else { // SI NO TIENE ESE TIPO DE LLAVE TODAVIA
                    if (!vis[h.destino]){ // Y EL NODO AUN NO HA SIDO VISITADO
                        aristas[h.tipo].push(h.destino); // GUARDA EL NODO COMO ALCANZABLE POTENCIAL POR SI SE LLEGA A ENCONTRAR UNA LLAVE DE ESE TIPO.
                    }
                }
            }

            if (ciclodoble) break;

            // RECOGE LA LLAVE DEL CUARTO Y MARCALA COMO ACTIVA
            if (!llave[r[nodo]]){ // SI NO HABIA ENCONTRADO ESE TIPO DE LLAVE
                llave[r[nodo]] = 1;
                while (!aristas[r[nodo]].empty()){ // SACA TODOS LOS NODOS A LOS QUE SE PODIA LLEGAR SI SE ENCONTRABA ESE TIPO DE LLAVE
                    int nod = aristas[r[nodo]].front();
                    aristas[r[nodo]].pop();
                    if (!vis[nod]){
                        if (ciclo[nod] != origen && ciclo[nod] != -1){
                            ciclodoble = true;
                            break;
                        }
                        vis[nod] = 1;
                        ++alcance;
                        q.push(nod);
                    }
                }
            }
	    }

        while(!q.empty()) q.pop();
        if (!ciclodoble && alcance < minimo){
            minimo = alcance;
            rep(i, 0, r.size() - 1){
                if (vis[i] == 1) ans[i] = 1;
                else ans[i] = 0;
            }
        }
        else if (!ciclodoble && alcance == minimo){
            rep(i, 0, r.size() - 1) if (vis[i] == 1) ans[i] = 1;
        }
    }

	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
keys.cpp:57:5: note: in expansion of macro 'rep'
   57 |     rep(i, 0, u.size() - 1){
      |     ^~~
keys.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
keys.cpp:65:5: note: in expansion of macro 'rep'
   65 |     rep(cuarto, 0, r.size() - 1) ciclo[cuarto] = -1;
      |     ^~~
keys.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
keys.cpp:66:5: note: in expansion of macro 'rep'
   66 |     rep(cuarto, 0, r.size() - 1) if (!visitado[cuarto]) dfs(cuarto);
      |     ^~~
keys.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
keys.cpp:133:13: note: in expansion of macro 'rep'
  133 |             rep(i, 0, r.size() - 1){
      |             ^~~
keys.cpp:7:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
      |                                         ^
keys.cpp:139:13: note: in expansion of macro 'rep'
  139 |             rep(i, 0, r.size() - 1) if (vis[i] == 1) ans[i] = 1;
      |             ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33