ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1072. Routing

please give me test #3
Posted by Иван 17 Oct 2014 00:59
my code:
WA on test 3

typedef uint32_t bitmap_t;

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

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

typedef struct {
unsigned int ip;
} 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];
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);
hosts[i].nic[j].ip = str2ip(ip);
}
}
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)) {
}
}
}
}
}

/*
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->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*/
}
return SUCC;
}
int pop(stack_t *st, int *val)
{
if (st->head == 0) {
return ERR;
} else {
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;
}
}
{
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;
}