ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1072. Маршрутизация

please give me test #3
Послано Иван 17 окт 2014 00:59
my code:
WA on test 3

typedef uint32_t bitmap_t;

typedef struct {
    int val[ST_SIZE];
    int head;
} stack_t;

typedef struct {
    int V; /*vertex*/
    int *p; /*parent*/
    char *c; /*color*/
    int *d; /*distance*/
    bitmap_t *adj; /*adjacency matrix*/
} graph_t;

typedef struct {
    unsigned int ip;
    unsigned int mask;
} nic_t;

typedef struct {
    int nnic;
    nic_t nic[MAX_NIC];
} host_t;

int main(void)
{
    int i, j, c, m, n, k;
    char ip[16];
    char mask[16];
    host_t *hosts;
    graph_t *gr;
    scanf("%d", &n);
    hosts = malloc(sizeof(host_t) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &k);
        hosts[i].nnic = k;
        for (j = 0; j < k; j++) {
            scanf("%s", ip);
            scanf("%s", mask);
            hosts[i].nic[j].ip = str2ip(ip);
            hosts[i].nic[j].mask = str2ip(mask);
        }
    }
    gr = initgraph(n);
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            for (c = 0; c < hosts[i].nnic; c++) {
                for (m = 0; m < hosts[j].nnic; m++) {
                    if ((hosts[i].nic[c].ip & hosts[i].nic[c].mask) ==
                    (hosts[j].nic[m].ip & hosts[j].nic[m].mask)) {
                        setadj(gr, i, j);
                    }
                }
            }
        }
    }

    /*
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%2d", (chkadj(gr, i, j)?1:0));
        }
        printf("\n");
    }
    */

    int sp, ep;
    scanf("%d%d", &sp, &ep);
    --sp; --ep;
    bfs(gr, ep);
    if (gr->c[sp] == WHITE) {
        printf("No\n");
        exit(0);
    }
    printf("Yes\n");
    print_path(gr, sp, ep);
    printf("\n");
    return 0;
}

void bfs(graph_t *gr, int sv)
{
    if (gr->V == 0)
        return;
    int i, u, v;
    for (i = 0; i < gr->V; i++) {
        gr->c[i] = WHITE;
        gr->d[i] = INFTY;
        gr->p[i] = NPARENT;
    }
    enqueue(sv);
    gr->d[sv] = 0;
    gr->c[sv] = GREY;
    for (; dequeue(&u);) {
        for (i = 0; i < gr->V; i++) {
            if (chkadj(gr, u, i)) {
                v = i;
                if (gr->c[v] == WHITE) {
                    gr->p[v] = u;
                    gr->d[v] = gr->d[u] + 1;
                    gr->c[v] = GREY;
                    enqueue(v);
                }
            }
        }
    }
}
void print_path(graph_t *gr, int sv, int ev)
{
    printf("%d ", sv + 1);
    if (sv == ev) {
        return;
    } else {
        print_path(gr, gr->p[sv], ev);
    }
}
graph_t *initgraph(int V)
{
    graph_t *gr;
    if ((gr = malloc(sizeof(graph_t))) == NULL)
        return NULL;
    gr->V = V;
    gr->adj = initadj(gr);
    gr->p = malloc(sizeof(int) * V);
    gr->c = malloc(sizeof(int) * V);
    gr->d = malloc(sizeof(int) * V);
    if (!gr->adj || !gr->p || !gr->c || !gr->d)
        return NULL;
    return gr;
}

stack_t st_in;
stack_t st_out;

int push(stack_t *st, int val)
{
    if (st->head == ST_SIZE) {
        return ERR; /*stack full*/
    }
    st->val[st->head] = val;
    st->head++;
    return SUCC;
}
int pop(stack_t *st, int *val)
{
    if (st->head == 0) {
        return ERR;
    } else {
        st->head--;
        *val = st->val[st->head];
        return SUCC;
    }
}
int enqueue(int val)
{
    if (push(&st_in, val) == ERR) {
        return ERR;
    } else {
        return SUCC;
    }
}
int dequeue(int *val)
{
    int tmp;
    if (pop(&st_out, &tmp) == ERR) { /*empty st_out*/
        if (pop(&st_in, &tmp) == ERR) { /*empty st_in*/
            return ERR;
        } else {
            push(&st_out, tmp);
        }
        for (;;) {
            if (pop(&st_in, &tmp) == ERR) {
                break;
            } else {
                push(&st_out, tmp);
            }
        }
        pop(&st_out, val);
        return SUCC;
    } else {
        *val = tmp;
        return SUCC;
    }
}
bitmap_t *initadj(graph_t *gr)
{
    int len;
    int V = gr->V;
    len = V * V / 2 - V / 2;
    return calloc(sizeof(bitmap_t), len / INT_BIT + 1);
}
bool chkadj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    return gr->adj[(row * n + col) / INT_BIT]
        & (1 << (row * n + col) % INT_BIT);
}
void setadj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    gr->adj[(row * n + col) / INT_BIT] =
        gr->adj[(row * n + col) / INT_BIT]
        | (1 << (row * n + col) % INT_BIT);
}
void deladj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    gr->adj[(row * n + col) / INT_BIT] =
        gr->adj[(row * n + col) / INT_BIT]
        & ~(1 << (row * n + col) % INT_BIT);
}
unsigned int str2ip(char *str)
{
    unsigned int r, b;
    for (r = 0, b = 0; *str != '\0'; str++) {
        if (*str == '.') {
            str++;
            r = r << 8;
            r += b;
            b = 0;
        }
        b = b * 10 + (*str - '0');
    }
    r = r << 8;
    r += b;
    return r;
}