diff options
| -rw-r--r-- | 924/in | 103 | ||||
| -rw-r--r-- | 924/news.cpp | 94 | ||||
| -rw-r--r-- | log.org | 4 |
3 files changed, 195 insertions, 6 deletions
@@ -0,0 +1,103 @@ +100 +7 8 25 15 50 77 43 87 +4 59 32 98 2 +0 +14 64 80 76 44 19 9 0 57 50 83 62 92 96 17 +3 57 53 94 +10 16 46 64 32 56 20 4 63 31 80 +9 46 0 33 56 61 59 83 64 29 +2 76 97 +4 59 85 52 9 +1 78 +14 83 68 75 79 40 60 39 11 32 31 8 67 16 73 +1 8 +8 65 41 38 23 75 33 4 73 +11 60 75 85 99 86 72 45 98 3 77 29 +3 86 3 31 +11 40 0 65 38 89 74 83 12 10 54 43 +3 66 75 57 +2 54 53 +10 58 55 37 45 7 67 13 90 56 16 +5 30 14 1 46 31 +6 89 82 50 53 31 29 +14 54 15 3 12 46 86 33 53 26 18 22 44 72 4 +6 78 34 54 49 65 29 +10 31 54 50 65 79 97 22 0 62 59 +11 6 13 0 33 40 43 70 10 75 99 88 +9 81 51 18 83 59 35 32 39 27 +14 42 46 41 94 72 50 48 44 49 78 9 58 8 38 +9 70 12 2 31 11 73 19 0 94 +5 9 6 74 31 65 +3 99 11 42 +1 50 +2 38 50 +1 89 +5 13 91 42 14 24 +3 63 34 93 +1 76 +5 56 39 81 90 57 +14 11 21 23 16 5 18 2 39 33 24 37 91 87 17 +11 65 19 46 4 89 34 95 5 43 73 68 +13 15 64 90 50 79 43 87 31 73 67 0 22 94 +1 76 +13 9 98 45 87 76 47 85 93 56 3 19 84 36 +4 92 8 6 62 +11 43 30 85 3 6 52 2 63 73 7 76 +14 43 97 4 31 39 96 56 19 25 24 89 36 18 79 +10 17 16 68 26 64 61 81 42 40 51 +3 86 53 97 +5 43 40 0 44 67 +14 20 48 32 55 51 71 18 11 3 60 80 52 92 67 +12 76 73 94 48 36 22 20 19 50 4 70 17 +10 63 73 99 0 61 40 72 75 95 31 +4 1 30 23 26 +5 36 32 93 89 53 +13 48 85 18 43 26 13 86 93 95 45 53 70 98 +0 +5 59 49 78 40 79 +6 76 86 8 32 99 49 +8 62 61 80 77 58 34 95 0 +10 75 57 67 30 90 95 61 51 42 58 +13 74 76 18 99 10 62 24 37 72 7 57 3 14 +7 55 3 49 43 29 56 4 +1 9 +14 66 64 82 87 75 29 47 74 78 79 17 8 50 44 +1 16 +11 88 22 9 79 54 43 29 45 74 44 33 +0 +8 94 12 29 61 76 9 93 39 +9 0 56 32 7 67 73 66 33 72 +3 31 9 45 +13 13 10 3 9 64 11 7 32 67 1 5 94 69 +14 28 10 6 44 96 21 3 67 1 27 93 24 29 84 +9 48 19 1 56 42 60 44 63 96 +13 6 88 70 87 61 41 32 67 24 17 59 52 46 +7 99 17 85 61 21 57 82 +3 36 61 27 +7 0 78 72 86 9 53 31 +1 11 +10 45 40 54 8 61 2 1 32 34 76 +11 22 15 13 14 18 49 30 65 96 44 12 +4 29 20 36 47 +3 51 46 38 +14 31 58 47 11 77 2 78 35 69 96 60 83 20 29 +14 96 13 16 27 42 97 57 82 41 84 72 28 68 75 +9 26 33 48 72 20 91 46 70 77 +0 +1 35 +2 13 69 +3 68 89 60 +11 12 98 2 46 56 30 83 28 85 14 63 +6 16 21 32 88 81 93 +3 85 18 97 +7 86 65 37 20 81 5 56 +12 2 38 80 29 18 9 81 0 64 6 88 46 +8 47 88 36 11 21 13 10 67 +4 2 4 24 10 +13 59 80 76 18 3 99 55 5 68 36 25 73 15 +8 24 72 17 36 39 15 82 48 +2 16 52 +9 99 80 11 8 4 2 30 43 61 +10 78 17 74 34 37 24 49 95 36 77 +1 +5
\ No newline at end of file diff --git a/924/news.cpp b/924/news.cpp index e48d241..e6b0385 100644 --- a/924/news.cpp +++ b/924/news.cpp @@ -1,14 +1,100 @@ #include <iostream> #include <vector> #include <queue> +#include <cstdlib> using namespace std; +int getNumUnique(queue<int>q){ + vector<int>seen; + int num_uniq = 0, curr; + bool repeat; + while(!q.empty()){ + repeat = false; + curr = q.front(); + q.pop(); + for(int i=0; i<seen.size(); i++){ + if(seen[i] == curr){ + repeat = true; + break; + } + } + if(!repeat){ + num_uniq++; + seen.push_back(curr); + } + } + return num_uniq; +} + +bool inQueue(queue<int>q, int num){ + int curr; + for(int i=0; i<q.size(); i++){ + curr = q.front(); + if(num == curr) + return true; + q.pop(); + } + return false; +} + int main(){ - int num_emps; + int num_emps, num_conns, emp; cin>>num_emps; - int *adj[num_emps]; - + vector<vector<int>>adj; + + /* Make adjecency matrix */ for(int i=0; i<num_emps; i++){ - arr[i] = (int*)malloc(num_emps*sizeof(int)); + cin>>num_conns; + vector<int> adj_list; + for(int j=0; j<num_conns; j++){ + cin>>emp; + adj_list.push_back(emp); + } + adj.push_back(adj_list); + } + + int tc, origin; + cin>>tc; + while(tc--){ + cin>>origin; + /* bfs vars */ + queue<int> q; + int max_num_depth, max_num, curr_size; + int visited[num_emps] = {0}, emp_depth[num_emps] = {0}; + int curr_emp, curr_depth = 0; + + q.push(origin); + curr_size = q.size(); + emp_depth[origin] = 0; + max_num_depth = 0; + max_num = 0; + + while(!q.empty()){ + curr_emp = q.front(); + visited[curr_emp] = 1; + if(emp_depth[curr_emp] > curr_depth){ /* depth increase */ + curr_depth+=1; + curr_size = getNumUnique(q); + if(curr_size > max_num){ + max_num_depth = curr_depth; + max_num = curr_size; + } + } + q.pop(); + + for(int i=0; i<adj[curr_emp].size(); i++){ + if(!visited[adj[curr_emp][i]] && + !inQueue(q, adj[curr_emp][i])){ + q.push(adj[curr_emp][i]); + /* If first time seeing this emp, increase emp depth */ + if(emp_depth[adj[curr_emp][i]] == 0) + emp_depth[adj[curr_emp][i]] = curr_depth+1; + } + } + } + if(max_num_depth == 0) + cout<<"0\n"; + else + cout<<max_num<<" "<<max_num_depth<<endl; } } @@ -13,5 +13,5 @@ - Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit) - Failed on TLE * TODO 924 -- Involves finding the graph depth maximum number of nodes from a given node -- BFS with keeping track of queue size at each depth +- Involves finding the depth with maximum number of nodes from a given node +- BFS with keeping track of queue sizes for each depth |