# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
436023 | 2021-06-24T05:37:15 Z | Ozy | 열쇠 (IOI21_keys) | C++17 | 1346 ms | 124988 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14284 KB | Output is correct |
2 | Correct | 10 ms | 14284 KB | Output is correct |
3 | Correct | 10 ms | 14388 KB | Output is correct |
4 | Correct | 11 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14380 KB | Output is correct |
6 | Correct | 12 ms | 14412 KB | Output is correct |
7 | Correct | 11 ms | 14284 KB | Output is correct |
8 | Correct | 11 ms | 14412 KB | Output is correct |
9 | Correct | 10 ms | 14284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14284 KB | Output is correct |
2 | Correct | 10 ms | 14284 KB | Output is correct |
3 | Correct | 10 ms | 14388 KB | Output is correct |
4 | Correct | 11 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14380 KB | Output is correct |
6 | Correct | 12 ms | 14412 KB | Output is correct |
7 | Correct | 11 ms | 14284 KB | Output is correct |
8 | Correct | 11 ms | 14412 KB | Output is correct |
9 | Correct | 10 ms | 14284 KB | Output is correct |
10 | Correct | 11 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14284 KB | Output is correct |
12 | Correct | 13 ms | 14284 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14364 KB | Output is correct |
15 | Correct | 11 ms | 14412 KB | Output is correct |
16 | Correct | 11 ms | 14284 KB | Output is correct |
17 | Correct | 11 ms | 14284 KB | Output is correct |
18 | Correct | 11 ms | 14284 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 11 ms | 14284 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14400 KB | Output is correct |
23 | Correct | 11 ms | 14408 KB | Output is correct |
24 | Correct | 11 ms | 14400 KB | Output is correct |
25 | Correct | 12 ms | 14284 KB | Output is correct |
26 | Correct | 11 ms | 14396 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14284 KB | Output is correct |
2 | Correct | 10 ms | 14284 KB | Output is correct |
3 | Correct | 10 ms | 14388 KB | Output is correct |
4 | Correct | 11 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14380 KB | Output is correct |
6 | Correct | 12 ms | 14412 KB | Output is correct |
7 | Correct | 11 ms | 14284 KB | Output is correct |
8 | Correct | 11 ms | 14412 KB | Output is correct |
9 | Correct | 10 ms | 14284 KB | Output is correct |
10 | Correct | 11 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14284 KB | Output is correct |
12 | Correct | 13 ms | 14284 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14364 KB | Output is correct |
15 | Correct | 11 ms | 14412 KB | Output is correct |
16 | Correct | 11 ms | 14284 KB | Output is correct |
17 | Correct | 11 ms | 14284 KB | Output is correct |
18 | Correct | 11 ms | 14284 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 11 ms | 14284 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14400 KB | Output is correct |
23 | Correct | 11 ms | 14408 KB | Output is correct |
24 | Correct | 11 ms | 14400 KB | Output is correct |
25 | Correct | 12 ms | 14284 KB | Output is correct |
26 | Correct | 11 ms | 14396 KB | Output is correct |
27 | Correct | 12 ms | 14456 KB | Output is correct |
28 | Correct | 12 ms | 14424 KB | Output is correct |
29 | Correct | 11 ms | 14412 KB | Output is correct |
30 | Correct | 13 ms | 14796 KB | Output is correct |
31 | Correct | 12 ms | 14412 KB | Output is correct |
32 | Correct | 11 ms | 14404 KB | Output is correct |
33 | Correct | 12 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 | 12 ms | 14444 KB | Output is correct |
37 | Correct | 11 ms | 14428 KB | Output is correct |
38 | Correct | 12 ms | 14412 KB | Output is correct |
39 | Correct | 14 ms | 14408 KB | Output is correct |
40 | Correct | 12 ms | 14516 KB | Output is correct |
41 | Correct | 13 ms | 14484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14284 KB | Output is correct |
2 | Correct | 10 ms | 14284 KB | Output is correct |
3 | Correct | 10 ms | 14388 KB | Output is correct |
4 | Correct | 11 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14380 KB | Output is correct |
6 | Correct | 12 ms | 14412 KB | Output is correct |
7 | Correct | 11 ms | 14284 KB | Output is correct |
8 | Correct | 11 ms | 14412 KB | Output is correct |
9 | Correct | 10 ms | 14284 KB | Output is correct |
10 | Correct | 125 ms | 24960 KB | Output is correct |
11 | Correct | 307 ms | 43804 KB | Output is correct |
12 | Correct | 73 ms | 20096 KB | Output is correct |
13 | Correct | 493 ms | 42352 KB | Output is correct |
14 | Correct | 352 ms | 89176 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 14284 KB | Output is correct |
2 | Correct | 10 ms | 14284 KB | Output is correct |
3 | Correct | 10 ms | 14388 KB | Output is correct |
4 | Correct | 11 ms | 14284 KB | Output is correct |
5 | Correct | 11 ms | 14380 KB | Output is correct |
6 | Correct | 12 ms | 14412 KB | Output is correct |
7 | Correct | 11 ms | 14284 KB | Output is correct |
8 | Correct | 11 ms | 14412 KB | Output is correct |
9 | Correct | 10 ms | 14284 KB | Output is correct |
10 | Correct | 11 ms | 14284 KB | Output is correct |
11 | Correct | 11 ms | 14284 KB | Output is correct |
12 | Correct | 13 ms | 14284 KB | Output is correct |
13 | Correct | 11 ms | 14284 KB | Output is correct |
14 | Correct | 11 ms | 14364 KB | Output is correct |
15 | Correct | 11 ms | 14412 KB | Output is correct |
16 | Correct | 11 ms | 14284 KB | Output is correct |
17 | Correct | 11 ms | 14284 KB | Output is correct |
18 | Correct | 11 ms | 14284 KB | Output is correct |
19 | Correct | 10 ms | 14284 KB | Output is correct |
20 | Correct | 11 ms | 14284 KB | Output is correct |
21 | Correct | 12 ms | 14412 KB | Output is correct |
22 | Correct | 11 ms | 14400 KB | Output is correct |
23 | Correct | 11 ms | 14408 KB | Output is correct |
24 | Correct | 11 ms | 14400 KB | Output is correct |
25 | Correct | 12 ms | 14284 KB | Output is correct |
26 | Correct | 11 ms | 14396 KB | Output is correct |
27 | Correct | 12 ms | 14456 KB | Output is correct |
28 | Correct | 12 ms | 14424 KB | Output is correct |
29 | Correct | 11 ms | 14412 KB | Output is correct |
30 | Correct | 13 ms | 14796 KB | Output is correct |
31 | Correct | 12 ms | 14412 KB | Output is correct |
32 | Correct | 11 ms | 14404 KB | Output is correct |
33 | Correct | 12 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 | 12 ms | 14444 KB | Output is correct |
37 | Correct | 11 ms | 14428 KB | Output is correct |
38 | Correct | 12 ms | 14412 KB | Output is correct |
39 | Correct | 14 ms | 14408 KB | Output is correct |
40 | Correct | 12 ms | 14516 KB | Output is correct |
41 | Correct | 13 ms | 14484 KB | Output is correct |
42 | Correct | 125 ms | 24960 KB | Output is correct |
43 | Correct | 307 ms | 43804 KB | Output is correct |
44 | Correct | 73 ms | 20096 KB | Output is correct |
45 | Correct | 493 ms | 42352 KB | Output is correct |
46 | Correct | 352 ms | 89176 KB | Output is correct |
47 | Correct | 10 ms | 14284 KB | Output is correct |
48 | Correct | 10 ms | 14284 KB | Output is correct |
49 | Correct | 11 ms | 14284 KB | Output is correct |
50 | Correct | 211 ms | 67968 KB | Output is correct |
51 | Correct | 175 ms | 34872 KB | Output is correct |
52 | Correct | 136 ms | 24452 KB | Output is correct |
53 | Correct | 136 ms | 24516 KB | Output is correct |
54 | Correct | 166 ms | 24572 KB | Output is correct |
55 | Correct | 126 ms | 24308 KB | Output is correct |
56 | Correct | 196 ms | 30604 KB | Output is correct |
57 | Correct | 162 ms | 29112 KB | Output is correct |
58 | Correct | 239 ms | 34356 KB | Output is correct |
59 | Correct | 973 ms | 124988 KB | Output is correct |
60 | Correct | 199 ms | 30020 KB | Output is correct |
61 | Correct | 190 ms | 30020 KB | Output is correct |
62 | Correct | 154 ms | 27076 KB | Output is correct |
63 | Correct | 259 ms | 37312 KB | Output is correct |
64 | Correct | 28 ms | 15644 KB | Output is correct |
65 | Correct | 37 ms | 15632 KB | Output is correct |
66 | Correct | 186 ms | 26992 KB | Output is correct |
67 | Correct | 145 ms | 21812 KB | Output is correct |
68 | Correct | 243 ms | 26776 KB | Output is correct |
69 | Correct | 945 ms | 121648 KB | Output is correct |
70 | Correct | 460 ms | 39180 KB | Output is correct |
71 | Correct | 1346 ms | 89412 KB | Output is correct |
72 | Correct | 985 ms | 124900 KB | Output is correct |
73 | Correct | 154 ms | 27080 KB | Output is correct |