diff options
| -rw-r--r-- | 924/in | 65 | ||||
| -rw-r--r-- | 924/news.cpp | 11 | ||||
| -rw-r--r-- | log.org | 6 |
3 files changed, 71 insertions, 11 deletions
@@ -4,7 +4,7 @@ 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 +11 16 46 64 32 56 20 4 63 31 5 80 9 46 0 33 56 61 59 83 64 29 2 76 97 4 59 85 52 9 @@ -99,5 +99,64 @@ 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 +59 +3 +4 +5 +6 +11 +12 +14 +15 +17 +19 +20 +21 +25 +30 +31 +35 +36 +37 +38 +39 +42 +43 +44 +46 +47 +48 +50 +51 +52 +53 +54 +55 +57 +58 +59 +60 +61 +62 +63 +65 +66 +68 +71 +72 +73 +74 +79 +81 +83 +84 +86 +87 +88 +92 +93 +94 +95 +98 +99 +p
\ No newline at end of file diff --git a/924/news.cpp b/924/news.cpp index e6b0385..2806260 100644 --- a/924/news.cpp +++ b/924/news.cpp @@ -27,8 +27,8 @@ int getNumUnique(queue<int>q){ } bool inQueue(queue<int>q, int num){ - int curr; - for(int i=0; i<q.size(); i++){ + int curr, qsize = q.size(); + for(int i=0; i<qsize; i++){ curr = q.front(); if(num == curr) return true; @@ -69,9 +69,9 @@ int main(){ max_num_depth = 0; max_num = 0; - while(!q.empty()){ + while(!q.empty()){ curr_emp = q.front(); - visited[curr_emp] = 1; + visited[curr_emp] = 1; if(emp_depth[curr_emp] > curr_depth){ /* depth increase */ curr_depth+=1; curr_size = getNumUnique(q); @@ -79,7 +79,7 @@ int main(){ max_num_depth = curr_depth; max_num = curr_size; } - } + } q.pop(); for(int i=0; i<adj[curr_emp].size(); i++){ @@ -92,6 +92,7 @@ int main(){ } } } + if(max_num_depth == 0) cout<<"0\n"; else @@ -7,11 +7,11 @@ - Word transformation: looks like a graph problem - Appears under 'easy BFS' - Needs to be revisited +* DONE 924 +- Involves finding the depth with maximum number of nodes from a given node +- BFS with keeping track of queue sizes for each depth * UNFINISHED 12532 - On uhunt this problem is put under 'tree-related structures', but not sure how a tree might be useful in this case - A segment tree perhaps? - 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 depth with maximum number of nodes from a given node -- BFS with keeping track of queue sizes for each depth |