AISD: pracownia D

• Pracownia D.

• Testy D.

http://www.ii.uni.wroc.pl/~mbi/dyd/aisd_10s/wyniki_D.html - wyniki

Runtime error na ostatnim. Rozwiazanie nie jest optymalne.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define CARMAX  100000
 
int i;
struct car {
        int     x;
        int     y;
        int     c;
} cars[CARMAX];
int path[CARMAX];
int dupa[CARMAX];
 
int cmp(struct car *a, struct car *b)
{
        return a->x != b->x ? a->x - b->x : a->y - b->y;
}
 
struct ll {
        struct ll       *prev;
        struct ll       *next;
        int             num;
        int             car;
        int             index;
} *list, *previous;
 
void dellt(struct ll *l, int c)
{
        struct ll       *tl;
        struct ll       *start = l;
        l = l->next;
        while (l) {
                if (c > l->car) {
                        tl = l->next; 
                        free(l);  
                        l = tl; 
                } else if (c <= l->car) {
                        l->prev = start;
                        start->next = l;
                        return;
                }
        }
        start->next = NULL;
}
 
void ins(int n, int c) {
        struct ll       *l = list;
        struct ll       *new;
        struct ll       *lt;
        if (previous && previous->num < n) {
                l = previous;
        }
 
        new             = malloc(sizeof(struct ll));
        new->num        = n;
        new->car        = c;
        new->index      = i;
        if (l == NULL) {
                new->next       = NULL;
                new->prev       = NULL;
                path[i]         = -1;
                list            = new;
                return;
        }
        while (l) {
                if (l->num == n) {
                        int     a = -1,
                                b = l->car;
                        if (l->prev)
                                a = l->prev->car;
                        if (a > b) {
                                l->car = c + a;
                                path[i] = l->prev->index; /* tu blad czasami powodujacy segfault */
                        } else {
                                l->car = c + b;
                                path[i] = l->index;
                        }
                        l->index = i;
                        dellt(l, l->car);
                        free(new); 
                        previous = l;
                        return;
                } else if (l->num > n) {
                        new->prev       = l->prev;
                        new->next       = l;
                        l->prev         = new;
                        if (new->prev) {
                                new->prev->next = new;
                                new->car += new->prev->car;
                                path[i] = new->prev->index;
                        } else {
                                list = new;
                                path[i] = -1;
                        }
                        dellt(new, new->car);
                        previous = new;
                        return;
                } else {
                        lt = l;
                        l = l->next;
                }
        }
        new->next = NULL;
        new->prev = lt;
        lt->next = new;
        if (new->prev) {
                path[i] = new->prev->index;
                new->car += new->prev->car;
        } else {
                path[i] = -1;
        }
        previous = new;
}
 
#define READ_INT(n)     n = 0; while((ch = getchar_unlocked()) >= '0') n = n * 10 + ch - '0';
int main()
{
        int m, n, k;
        char ch;
 
        /* scanf("%d %d %d", &m, &n, &k); */
        READ_INT(m);
        READ_INT(n);
        READ_INT(k);
        memset(path, -1, CARMAX*4);
        for (i = 0; i < k; i++) {
                READ_INT(cars[i].x);
                READ_INT(cars[i].y);
                READ_INT(cars[i].c);
                /* scanf("%d %d %d", &cars[i].x, &cars[i].y, &cars[i].c); */
        }
        qsort(cars, k, sizeof(struct car), (int (*)(const void *, const void *))cmp);
 
        for (i = 0; i < k; i++) {
                /* if(!(i % 100)) { printf("%d\n", i);} */
                ins(cars[i].y, cars[i].c); 
        }
        while (list->next) list = list->next;
        m = 0;
        i = list->index;
        while (i != -1) {
                dupa[m] = i;
                i = path[i];
                m++;
        }
        printf("%d\n%d\n", list->car, m);
        while (m > 0) {
                m--;
                printf("%d %d\n", cars[dupa[m]].x, cars[dupa[m]].y);
        }
        return 0;
}