/home/toolbox/public_html/solutions/9/924/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2021-12-15
19 * Purpose: fun
20 * Problem: 924 - Spread the News
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 */
26
27 #define MAX_EMPLOYEES 2505
28 #define MAX_FRIENDS 16
29 #define DOES_NOT_KNOW 0
30 #define JUST_FOUND_OUT 1
31 #define KNOWS 2
32 #define HAS_KNOWN 3
33 #define EMPTY -1
34 #define PREVIOUS 0
35 #define CURRENT 1
36
37 int e[MAX_EMPLOYEES][MAX_FRIENDS];
38 int eCnt;
39 int news[MAX_EMPLOYEES];
40 int stack[2][MAX_EMPLOYEES]; /* 2 stacks peoplle who found out lst time and people finding out now */
41 int stackTop[2];
42 int qCnt;
43 int query;
44
45 void init()
46 {
47 /* FUNCTION init */
48 int i;
49
50 for (i=0; eCnt>i; i++)
51 {
52 news[i] = DOES_NOT_KNOW;
53 }
54 stackTop[PREVIOUS] = EMPTY;
55 stackTop[CURRENT] = EMPTY;
56 } /* FUNCTION init */
57
58 void dump()
59 {
60 /* FUNCTION dump */
61 } /* FUNCTION dump */
62
63 void getInput()
64 {
65 /* FUNCTION getInput */
66 int i;
67 int j;
68
69 scanf(" %d ", &eCnt);
70 for (i=0; eCnt>i; i++)
71 {
72 /* for each employee */
73 scanf(" %d ", &e[i][0]);
74 for (j=1; e[i][0]>=j; j++)
75 {
76 /* for each friend */
77 scanf(" %d ", &e[i][j]);
78 } /* for each friend */
79 } /* for each employee */
80 scanf(" %d ", &qCnt);
81 } /* FUNCTION getInput */
82
83 void push(int stk, int x)
84 {
85 /* FUNCTION push */
86 stackTop[stk]++;
87 stack[stk][stackTop[stk]] = x;
88 } /* FUNCTION push */
89
90 int pop(int stk)
91 {
92 /* FUNCTION pop */
93 return stack[stk][stackTop[stk]--];
94 } /* FUNCTION pop */
95
96 void process()
97 {
98 /* FUNCTION process */
99 int i;
100 int bestCnt;
101 int bestDay;
102 int cnt;
103 int day;
104 int k;
105 int m;
106
107 for (i=0; qCnt>i; i++)
108 {
109 /* for each query */
110 init();
111 scanf(" %d ", &query);
112 push(PREVIOUS, query);
113 bestCnt = e[query][0];
114 bestDay = 1;
115 day = 1;
116 do
117 {
118 /* do while */
119 DEBUG printf("(Day %d) (bestCnt %d) (bestDay %d)\n", day, bestCnt, bestDay);
120 DEBUG printf("A day %d\n", day);
121 cnt = 0;
122 DEBUG printf("B day %d\n", day);
123 while (EMPTY != stackTop[PREVIOUS])
124 {
125 /* figure out who is just now learning */
126 query = pop(PREVIOUS);
127 news[query] = KNOWS;
128 DEBUG printf("Processing %d | stack still has %d\n", query, stackTop[PREVIOUS]);
129 for (m=1; e[query][0] >= m; m++)
130 {
131 /* for each friend of the query */
132 if (DOES_NOT_KNOW == news[e[query][m]])
133 {
134 /* some one learning now */
135 DEBUG printf("new person %d\n", e[query][m]);
136 push(CURRENT, e[query][m]);
137 news[e[query][m]] = KNOWS;
138 } /* some one learning now */
139 } /* for each friend of the query */
140 } /* figure out who is just now learning */
141 while (EMPTY != stackTop[CURRENT])
142 {
143 /* move current to previous */
144 push(PREVIOUS, pop(CURRENT));
145 cnt++;
146 } /* move current to previous */
147 DEBUG printf("C day %d\n", day);
148 if (cnt > bestCnt)
149 {
150 /* found a bigger bloom */
151 bestCnt = cnt;
152 bestDay = day;
153 DEBUG printf("Resetting best: %d %d\n", bestCnt, bestDay);
154 } /* found a bigger bloom */
155 day++;
156 } /* do while */
157 while (0 < cnt);
158 printf("%d", bestCnt);
159 if (0 < bestCnt)
160 {
161 printf(" %d", bestDay);
162 }
163 printf("\n");
164 } /* for each query */
165 } /* FUNCTION process */
166
167 int main()
168 {
169 /* main */
170 int moreToDo;
171
172 getInput();
173 process();
174
175 return EXIT_SUCCESS;
176 } /* main */
177