oj.uz

답안 #435046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435046 2021-06-22T21:26:25 Z Ozy 열쇠 (IOI21_keys) C++17
37 / 100
 651 ms 17132 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 7 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 444 KB Output is correct
9 Correct 5 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 7 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 444 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 6 ms 484 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 5 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 5 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 476 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 7 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 444 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 6 ms 484 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 5 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 5 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 476 KB Output is correct
27 Correct 506 ms 1844 KB Output is correct
28 Correct 508 ms 1848 KB Output is correct
29 Correct 512 ms 1944 KB Output is correct
30 Correct 112 ms 972 KB Output is correct
31 Correct 112 ms 1092 KB Output is correct
32 Correct 11 ms 460 KB Output is correct
33 Correct 72 ms 932 KB Output is correct
34 Correct 134 ms 972 KB Output is correct
35 Correct 106 ms 912 KB Output is correct
36 Correct 452 ms 1496 KB Output is correct
37 Correct 422 ms 1488 KB Output is correct
38 Correct 651 ms 1824 KB Output is correct
39 Correct 642 ms 1752 KB Output is correct
40 Correct 117 ms 1100 KB Output is correct
41 Correct 161 ms 1136 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 7 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 444 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Runtime error 110 ms 17132 KB Execution killed with signal 11
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 7 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 444 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 6 ms 484 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 5 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 5 ms 332 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 476 KB Output is correct
27 Correct 506 ms 1844 KB Output is correct
28 Correct 508 ms 1848 KB Output is correct
29 Correct 512 ms 1944 KB Output is correct
30 Correct 112 ms 972 KB Output is correct
31 Correct 112 ms 1092 KB Output is correct
32 Correct 11 ms 460 KB Output is correct
33 Correct 72 ms 932 KB Output is correct
34 Correct 134 ms 972 KB Output is correct
35 Correct 106 ms 912 KB Output is correct
36 Correct 452 ms 1496 KB Output is correct
37 Correct 422 ms 1488 KB Output is correct
38 Correct 651 ms 1824 KB Output is correct
39 Correct 642 ms 1752 KB Output is correct
40 Correct 117 ms 1100 KB Output is correct
41 Correct 161 ms 1136 KB Output is correct
42 Runtime error 110 ms 17132 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -