Submission #436022

#	Time	Username	Problem	Language	Result	Execution time	Memory
436022		ocarima	Keys (IOI21_keys)	C++17	100 / 100	1390 ms	125016 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], cicloprocesado[MAX_N], minimo, origen, alcance;
vector<pair<int, int> > largociclo;
stack<int> s;
bool desechado, existehoja;


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.empty() && s.top() != h){
                ciclo[s.top()] = h;
                nodosciclo[h].push_back(s.top());
                visitado[s.top()] = 3;
                s.pop();
            }
            nodosciclo[h].push_back(h);
            ciclo[h] = h;
            visitado[h] = 3;
            if (!s.empty()) s.pop();

            largociclo.emplace_back(nodosciclo[h].size(), h);
        }
        else if (visitado[h] == 3){ // SE UNIO A UN CICLO QUE YA EXISTE
            while (!s.empty() && ciclo[s.top()] == -1){
                ciclo[s.top()] = ciclo[h];
                nodosciclo[h].push_back(s.top());
                visitado[s.top()] = 3;
                s.pop();
            }
        }
    }
    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(), 0);

    // 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
    }

    // VERIFICA SI HAY ALGUN CUARTO CON ALCANCE 0
    existehoja = false;
    rep(cuarto, 0, r.size() - 1) if (hijos[cuarto].size() == 0){
        existehoja = true;
        break;
    }
    if (existehoja){
        rep(cuarto, 0, r.size() - 1) if (hijos[cuarto].size() == 0) ans[cuarto] = 1;
        return ans;
    }

    // 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() + 1;

    // AGREGA TODAS LAS ARISTAS PARA PODER VER EL ALCANCE
    rep(cuarto, 0, r.size() - 1) hijos[cuarto].clear();
    rep(i, 0, c.size() - 1){
        hijos[u[i]].emplace_back(v[i], c[i]);
        hijos[v[i]].emplace_back(u[i], c[i]);
    }

    // PARA CADA CICLO REVISA EL ALCANCE QUE TIENE
    vector<int> vis(r.size(), -1); // PERMITE SABER QUE NODOS YA FUERON VISITADOS
    vector<int> llave(r.size(), -1); // PERMITE SABER QUE LLAVES YA SE TIENEN
    queue<int> q;

    for (auto c : largociclo){
        if (c.first > minimo) break;
        origen = c.second;
        alcance = 0;
        desechado = false;

        map<int, queue<int> > aristas; // PERMITE GUARDAR LAS ARISTAS QUE SE ACTIVARAN SI SE ENCUENTRA UN TIPO DE LLAVE
        vector<int> alcanzado;

	    vis[origen] = origen; // VISITA EL NODO ACTUAL
	    alcanzado.push_back(origen);
	    alcance = 1;
	    q.push(origen);

	    while (!q.empty()){
            if (alcance > minimo){
                desechado = true;
                break;
            }
            int nodo = q.front();
            q.pop();

            if (cicloprocesado[nodo] > 0){
                desechado = true;
                break;
            }

            for (auto h : hijos[nodo]){ // REVISA TODOS LOS NODOS A LOS QUE ESTA CONECTADO
                if (llave[h.tipo] == origen){ // SI YA TIENE EL TIPO DE LLAVE NECESARIO
                    if (vis[h.destino] != origen){ // Y EL NODO NO HA SIDO VISITADO, ENTONCES VISITALO Y AGREGALO A LA COLA
                        vis[h.destino] = origen;
                        alcanzado.push_back(h.destino);
                        ++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] != origen){ // 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.
                    }
                }
            }

            // RECOGE LA LLAVE DEL CUARTO Y MARCALA COMO ACTIVA
            if (llave[r[nodo]] != origen){ // SI NO HABIA ENCONTRADO ESE TIPO DE LLAVE
                llave[r[nodo]] = origen;
                if (aristas.find(r[nodo]) != aristas.end()){
                    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] != origen){
                            vis[nod] = origen;
                            alcanzado.push_back(nod);
                            ++alcance;
                            q.push(nod);
                        }
                    }
                    aristas.erase(r[nodo]);
                }
            }
	    }

        while(!q.empty()) q.pop();

        for(auto n : nodosciclo[origen]) cicloprocesado[n] = 1;

        if (!desechado && alcance < minimo){
            minimo = alcance;
            vector<int> ().swap(ans);
            ans.resize(r.size(), 0);
            for(auto a : alcanzado) ans[a] = 1;
        }
        else if (!desechado && alcance == minimo){
            for(auto a : alcanzado) ans[a] = 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:66:5: note: in expansion of macro 'rep'
   66 |     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:73:5: note: in expansion of macro 'rep'
   73 |     rep(cuarto, 0, r.size() - 1) if (hijos[cuarto].size() == 0){
      |     ^~~
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:78:9: note: in expansion of macro 'rep'
   78 |         rep(cuarto, 0, r.size() - 1) if (hijos[cuarto].size() == 0) ans[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:85:5: note: in expansion of macro 'rep'
   85 |     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:86:5: note: in expansion of macro 'rep'
   86 |     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:92:5: note: in expansion of macro 'rep'
   92 |     rep(cuarto, 0, r.size() - 1) hijos[cuarto].clear();
      |     ^~~
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:93:5: note: in expansion of macro 'rep'
   93 |     rep(i, 0, c.size() - 1){
      |     ^~~

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