oj.uz

답안 #435040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435040 2021-06-22T21:19:26 Z ocarima 열쇠 (IOI21_keys) C++17
37 / 100
 661 ms 17124 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 2002

#define destino first
#define tipo second

int minimo = MAX_N + 1;
int tamano[MAX_N]; // TAMAÑO DEL CONJUNTO ALCANZABLE DESDE EL NODO i


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 EL GRAFO PARA PODER HACER LA BUSQUEDA DE FORMA SENCILLA SIN TENER QUE RECORRER TODAS LAS ARISTAS
	vector<pair<int, int> > hijos[MAX_N];
	rep(i, 0, u.size() - 1){
	    hijos[u[i]].emplace_back(v[i], c[i]);
	    hijos[v[i]].emplace_back(u[i], c[i]);
	}

	// INTENTA RESOLVER PARA CADA NODO INICIAL
	rep(n, 0, r.size() - 1){
	    int alcanzados = 0;
	    vector<int> visitado(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;

	    visitado[n] = 1; // VISITA EL NODO ACTUAL
	    alcanzados = 1;
	    q.push(n);
	    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 (!visitado[h.destino]){ // Y EL NODO NO HA SIDO VISITADO, ENTONCES VISITALO Y AGREGALO A LA COLA
                        visitado[h.destino] = 1;
                        ++alcanzados;
                        q.push(h.destino);
                    }
                    // SI YA FUE VISITADO NO ES NECESARIO HACER NADA
                }
                else { // SI NO TIENE ESE TIPO DE LLAVE TODAVIA
                    if (!visitado[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.
                    }
                }
            }

            // 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 (!visitado[nod]){
                        visitado[nod] = 1;
                        ++alcanzados;
                        q.push(nod);
                    }
                }
            }
	    }

	    minimo = min(minimo, alcanzados);
	    tamano[n] = alcanzados;
	}

	rep(i, 0, r.size() - 1) ans[i] = (tamano[i] == minimo) ? 1 : 0;

	return ans;
}

Compilation message

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:29:2: note: in expansion of macro 'rep'
   29 |  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:35:2: note: in expansion of macro 'rep'
   35 |  rep(n, 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:83:2: note: in expansion of macro 'rep'
   83 |  rep(i, 0, r.size() - 1) ans[i] = (tamano[i] == minimo) ? 1 : 0;
      |  ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 6 ms 484 KB Output is correct
11 Correct 6 ms 488 KB Output is correct
12 Correct 6 ms 480 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 6 ms 460 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 6 ms 472 KB Output is correct
26 Correct 6 ms 480 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 6 ms 484 KB Output is correct
11 Correct 6 ms 488 KB Output is correct
12 Correct 6 ms 480 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 6 ms 460 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 6 ms 472 KB Output is correct
26 Correct 6 ms 480 KB Output is correct
27 Correct 513 ms 1848 KB Output is correct
28 Correct 508 ms 1856 KB Output is correct
29 Correct 517 ms 1868 KB Output is correct
30 Correct 111 ms 960 KB Output is correct
31 Correct 108 ms 972 KB Output is correct
32 Correct 12 ms 460 KB Output is correct
33 Correct 70 ms 844 KB Output is correct
34 Correct 161 ms 1092 KB Output is correct
35 Correct 102 ms 1024 KB Output is correct
36 Correct 478 ms 1600 KB Output is correct
37 Correct 408 ms 1608 KB Output is correct
38 Correct 658 ms 1744 KB Output is correct
39 Correct 661 ms 1828 KB Output is correct
40 Correct 116 ms 1100 KB Output is correct
41 Correct 146 ms 1156 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Runtime error 112 ms 17124 KB Execution killed with signal 7
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 7 ms 460 KB Output is correct
10 Correct 6 ms 484 KB Output is correct
11 Correct 6 ms 488 KB Output is correct
12 Correct 6 ms 480 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 6 ms 460 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 6 ms 472 KB Output is correct
26 Correct 6 ms 480 KB Output is correct
27 Correct 513 ms 1848 KB Output is correct
28 Correct 508 ms 1856 KB Output is correct
29 Correct 517 ms 1868 KB Output is correct
30 Correct 111 ms 960 KB Output is correct
31 Correct 108 ms 972 KB Output is correct
32 Correct 12 ms 460 KB Output is correct
33 Correct 70 ms 844 KB Output is correct
34 Correct 161 ms 1092 KB Output is correct
35 Correct 102 ms 1024 KB Output is correct
36 Correct 478 ms 1600 KB Output is correct
37 Correct 408 ms 1608 KB Output is correct
38 Correct 658 ms 1744 KB Output is correct
39 Correct 661 ms 1828 KB Output is correct
40 Correct 116 ms 1100 KB Output is correct
41 Correct 146 ms 1156 KB Output is correct
42 Runtime error 112 ms 17124 KB Execution killed with signal 7
43 Halted 0 ms 0 KB -