Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Tuenti Contest
- * Challenge 4 - Task Durations
- * Author: Pedro Antonio Pardal Jimena
- * Email: pardal@alu.uma.es
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define IN_FILENAME "in"
- #define BUFFER_SIZE 0x1000
- struct node
- {
- unsigned int cost, child, brother;
- };
- struct node_search
- {
- unsigned int tid, cost;
- };
- int total;
- struct node *table;
- int stack_ptr = 0;
- struct node_search *stack;
- #define stack_empty !stack_ptr
- static inline void stack_push(struct node_search nod)
- {
- stack[stack_ptr++] = nod;
- }
- static inline struct node_search stack_pop()
- {
- return stack[--stack_ptr];
- }
- char buffer[BUFFER_SIZE];
- static void read_table()
- {
- int i, tid, cost, depends, brother;
- char *tok;
- FILE *in;
- in = fopen(IN_FILENAME, "r");
- if (in == NULL)
- {
- perror("fopen");
- exit(-1);
- }
- while (fgets(buffer, BUFFER_SIZE, in) != NULL)
- {
- if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
- {
- total = atoi(buffer);
- table = (struct node *) malloc(total*sizeof(struct node));
- stack = (struct node_search *) malloc(total*sizeof(struct node_search));
- break;
- }
- }
- for (i = 0; i < total; i++)
- {
- if (fgets(buffer, BUFFER_SIZE, in) == NULL)
- {
- perror("fgets");
- exit(-1);
- }
- if (buffer[0] == '#' || buffer[0] == '\0' || buffer[0] == '\n')
- {
- i--;
- continue;
- }
- tok = strtok(buffer, ",\n");
- tid = atoi(tok);
- tok = strtok(NULL, ",\n");
- cost = atoi(tok);
- table[tid].cost = cost;
- table[tid].child = -1;
- table[tid].brother = -1;
- }
- while (fgets(buffer, BUFFER_SIZE, in) != NULL)
- {
- if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
- {
- tok = strtok(buffer, ",\n");
- tid = atoi(tok);
- brother = -1;
- while ((tok = strtok(NULL, ",\n")) != NULL)
- {
- depends = atoi(tok);
- table[depends].brother = brother;
- brother = depends;
- }
- table[tid].child = brother;
- }
- }
- fclose(in);
- }
- static void print_table()
- {
- int i;
- for (i = 0; i < total; i++)
- {
- printf("Task %d: Cost->%d, Child->%d, Brother->%d\n",
- i, table[i].cost, table[i].child, table[i].brother);
- }
- }
- static int compute_cost(int tid)
- {
- struct node_search nod = {.tid = tid, .cost = table[tid].cost};
- int maxcost = -1, childcost = -1, child = -1;
- stack_push(nod);
- while (!stack_empty)
- {
- nod = stack_pop();
- childcost = nod.cost;
- if (childcost > maxcost)
- maxcost = childcost;
- child = table[nod.tid].child;
- while (child != -1)
- {
- nod.tid = child;
- nod.cost = table[child].cost + childcost;
- stack_push(nod);
- child = table[child].brother;
- }
- }
- return maxcost;
- }
- int main(int argc, char *argv[])
- {
- char *tok;
- int tid, cost;
- read_table();
- if (fgets(buffer, BUFFER_SIZE, stdin) == NULL)
- {
- perror("fgets");
- exit(-1);
- }
- tok = strtok(buffer, ",\n");
- do
- {
- tid = atoi(tok);
- cost = compute_cost(tid);
- fprintf(stdout, "%d %d\n", tid, cost);
- }
- while ((tok = strtok(NULL, ",\n")) != NULL);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement