# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
436022 | 2021-06-24T05:36:03 Z | ocarima | Keys (IOI21_keys) | C++17 | 1390 ms | 125016 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14348 KB | Output is correct |
2 | Correct | 11 ms | 14412 KB | Output is correct |
3 | Correct | 10 ms | 14284 KB | Output is correct |
4 | Correct | 12 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14284 KB | Output is correct |
6 | Correct | 14 ms | 14284 KB | Output is correct |
7 | Correct | 11 ms | 14392 KB | Output is correct |
8 | Correct | 13 ms | 14412 KB | Output is correct |
9 | Correct | 12 ms | 14412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14348 KB | Output is correct |
2 | Correct | 11 ms | 14412 KB | Output is correct |
3 | Correct | 10 ms | 14284 KB | Output is correct |
4 | Correct | 12 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14284 KB | Output is correct |
6 | Correct | 14 ms | 14284 KB | Output is correct |
7 | Correct | 11 ms | 14392 KB | Output is correct |
8 | Correct | 13 ms | 14412 KB | Output is correct |
9 | Correct | 12 ms | 14412 KB | Output is correct |
10 | Correct | 10 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14312 KB | Output is correct |
12 | Correct | 11 ms | 14308 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14284 KB | Output is correct |
15 | Correct | 11 ms | 14464 KB | Output is correct |
16 | Correct | 13 ms | 14384 KB | Output is correct |
17 | Correct | 10 ms | 14284 KB | Output is correct |
18 | Correct | 12 ms | 14412 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 10 ms | 14412 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14284 KB | Output is correct |
23 | Correct | 10 ms | 14284 KB | Output is correct |
24 | Correct | 11 ms | 14388 KB | Output is correct |
25 | Correct | 11 ms | 14288 KB | Output is correct |
26 | Correct | 10 ms | 14296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14348 KB | Output is correct |
2 | Correct | 11 ms | 14412 KB | Output is correct |
3 | Correct | 10 ms | 14284 KB | Output is correct |
4 | Correct | 12 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14284 KB | Output is correct |
6 | Correct | 14 ms | 14284 KB | Output is correct |
7 | Correct | 11 ms | 14392 KB | Output is correct |
8 | Correct | 13 ms | 14412 KB | Output is correct |
9 | Correct | 12 ms | 14412 KB | Output is correct |
10 | Correct | 10 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14312 KB | Output is correct |
12 | Correct | 11 ms | 14308 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14284 KB | Output is correct |
15 | Correct | 11 ms | 14464 KB | Output is correct |
16 | Correct | 13 ms | 14384 KB | Output is correct |
17 | Correct | 10 ms | 14284 KB | Output is correct |
18 | Correct | 12 ms | 14412 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 10 ms | 14412 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14284 KB | Output is correct |
23 | Correct | 10 ms | 14284 KB | Output is correct |
24 | Correct | 11 ms | 14388 KB | Output is correct |
25 | Correct | 11 ms | 14288 KB | Output is correct |
26 | Correct | 10 ms | 14296 KB | Output is correct |
27 | Correct | 14 ms | 14428 KB | Output is correct |
28 | Correct | 12 ms | 14412 KB | Output is correct |
29 | Correct | 12 ms | 14412 KB | Output is correct |
30 | Correct | 12 ms | 14796 KB | Output is correct |
31 | Correct | 11 ms | 14368 KB | Output is correct |
32 | Correct | 11 ms | 14412 KB | Output is correct |
33 | Correct | 11 ms | 14412 KB | Output is correct |
34 | Correct | 32 ms | 14540 KB | Output is correct |
35 | Correct | 12 ms | 14412 KB | Output is correct |
36 | Correct | 11 ms | 14440 KB | Output is correct |
37 | Correct | 12 ms | 14504 KB | Output is correct |
38 | Correct | 14 ms | 14412 KB | Output is correct |
39 | Correct | 12 ms | 14412 KB | Output is correct |
40 | Correct | 15 ms | 14408 KB | Output is correct |
41 | Correct | 15 ms | 14548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14348 KB | Output is correct |
2 | Correct | 11 ms | 14412 KB | Output is correct |
3 | Correct | 10 ms | 14284 KB | Output is correct |
4 | Correct | 12 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14284 KB | Output is correct |
6 | Correct | 14 ms | 14284 KB | Output is correct |
7 | Correct | 11 ms | 14392 KB | Output is correct |
8 | Correct | 13 ms | 14412 KB | Output is correct |
9 | Correct | 12 ms | 14412 KB | Output is correct |
10 | Correct | 131 ms | 24964 KB | Output is correct |
11 | Correct | 325 ms | 43788 KB | Output is correct |
12 | Correct | 73 ms | 20096 KB | Output is correct |
13 | Correct | 455 ms | 42352 KB | Output is correct |
14 | Correct | 437 ms | 89096 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14348 KB | Output is correct |
2 | Correct | 11 ms | 14412 KB | Output is correct |
3 | Correct | 10 ms | 14284 KB | Output is correct |
4 | Correct | 12 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14284 KB | Output is correct |
6 | Correct | 14 ms | 14284 KB | Output is correct |
7 | Correct | 11 ms | 14392 KB | Output is correct |
8 | Correct | 13 ms | 14412 KB | Output is correct |
9 | Correct | 12 ms | 14412 KB | Output is correct |
10 | Correct | 10 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14312 KB | Output is correct |
12 | Correct | 11 ms | 14308 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14284 KB | Output is correct |
15 | Correct | 11 ms | 14464 KB | Output is correct |
16 | Correct | 13 ms | 14384 KB | Output is correct |
17 | Correct | 10 ms | 14284 KB | Output is correct |
18 | Correct | 12 ms | 14412 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 10 ms | 14412 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14284 KB | Output is correct |
23 | Correct | 10 ms | 14284 KB | Output is correct |
24 | Correct | 11 ms | 14388 KB | Output is correct |
25 | Correct | 11 ms | 14288 KB | Output is correct |
26 | Correct | 10 ms | 14296 KB | Output is correct |
27 | Correct | 14 ms | 14428 KB | Output is correct |
28 | Correct | 12 ms | 14412 KB | Output is correct |
29 | Correct | 12 ms | 14412 KB | Output is correct |
30 | Correct | 12 ms | 14796 KB | Output is correct |
31 | Correct | 11 ms | 14368 KB | Output is correct |
32 | Correct | 11 ms | 14412 KB | Output is correct |
33 | Correct | 11 ms | 14412 KB | Output is correct |
34 | Correct | 32 ms | 14540 KB | Output is correct |
35 | Correct | 12 ms | 14412 KB | Output is correct |
36 | Correct | 11 ms | 14440 KB | Output is correct |
37 | Correct | 12 ms | 14504 KB | Output is correct |
38 | Correct | 14 ms | 14412 KB | Output is correct |
39 | Correct | 12 ms | 14412 KB | Output is correct |
40 | Correct | 15 ms | 14408 KB | Output is correct |
41 | Correct | 15 ms | 14548 KB | Output is correct |
42 | Correct | 131 ms | 24964 KB | Output is correct |
43 | Correct | 325 ms | 43788 KB | Output is correct |
44 | Correct | 73 ms | 20096 KB | Output is correct |
45 | Correct | 455 ms | 42352 KB | Output is correct |
46 | Correct | 437 ms | 89096 KB | Output is correct |
47 | Correct | 11 ms | 14284 KB | Output is correct |
48 | Correct | 11 ms | 14400 KB | Output is correct |
49 | Correct | 10 ms | 14284 KB | Output is correct |
50 | Correct | 283 ms | 67952 KB | Output is correct |
51 | Correct | 201 ms | 34812 KB | Output is correct |
52 | Correct | 143 ms | 24576 KB | Output is correct |
53 | Correct | 144 ms | 24504 KB | Output is correct |
54 | Correct | 142 ms | 24560 KB | Output is correct |
55 | Correct | 131 ms | 24320 KB | Output is correct |
56 | Correct | 212 ms | 30596 KB | Output is correct |
57 | Correct | 189 ms | 29176 KB | Output is correct |
58 | Correct | 244 ms | 34304 KB | Output is correct |
59 | Correct | 1026 ms | 125016 KB | Output is correct |
60 | Correct | 217 ms | 30036 KB | Output is correct |
61 | Correct | 197 ms | 29960 KB | Output is correct |
62 | Correct | 205 ms | 27076 KB | Output is correct |
63 | Correct | 290 ms | 37376 KB | Output is correct |
64 | Correct | 28 ms | 15564 KB | Output is correct |
65 | Correct | 37 ms | 15648 KB | Output is correct |
66 | Correct | 162 ms | 27008 KB | Output is correct |
67 | Correct | 172 ms | 21788 KB | Output is correct |
68 | Correct | 237 ms | 26776 KB | Output is correct |
69 | Correct | 1030 ms | 121676 KB | Output is correct |
70 | Correct | 472 ms | 39284 KB | Output is correct |
71 | Correct | 1390 ms | 89316 KB | Output is correct |
72 | Correct | 1055 ms | 124904 KB | Output is correct |
73 | Correct | 154 ms | 27076 KB | Output is correct |