125 - Numbering Ways - WA

[gosdep]

Hello, guys, I need your help in problem 125. My algorithm seems to be correct and it gives right answers to all inputs known to me, but it still gets WA.

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 35
               
int main() {

  int n, cities, step, i, j, k, c, count, curNeighbour, case_no;
  int graph_matrix[SIZE][SIZE][SIZE], sum_matrix[SIZE][SIZE];
  int neighbours [SIZE][SIZE];
  int n_counter [SIZE];
  int cycled_vertices[SIZE], good_vertices[SIZE];
  int cycled_vertices_num, good_vertices_num;
 
  case_no = -1;
  while (1) {
     if (scanf ("%d", &n) == 1) {       
        case_no++;
       
        if (n == 0) {
           printf ("matrix for city %d\n", case_no);
           continue;
        };
       
        for (i=0; i<30; i++) {
            n_counter[i] = 0;
            for (j=0; j<30; j++) {
                graph_matrix [0][i][j] = 0;
                neighbours[i][j] = -1;
            }     
        }
       
        cities = 0;
        for (k=0; k<n; k++) {
            scanf ("%d %d", &i, &j);
            if (i>cities)
               cities = i;
            if (j>cities)
               cities = j;           
            graph_matrix[0][i][j] = 1;
            neighbours[i][ n_counter[i] ] = j;
            n_counter[i]++;
        }
        cities++;
       
        /* Iterative DP */
        step = 1;
        for (k=0; k<cities-1; k++) {
            for (i=0; i<cities; i++)
                for (j=0; j<cities; j++) {
                     count = 0;
                     curNeighbour = 0;
                     while (neighbours[i][curNeighbour] > -1) {
                          count += graph_matrix [step-1][ neighbours[i][curNeighbour] ][j];
                          curNeighbour++;
                     }
                     graph_matrix[step][i][j] = count;
                }
           
            step++;
        }
       
        for (i=0; i<cities; i++)
            for (j=0; j<cities; j++) {
                count = 0;
                for (k=0; k<cities; k++)
                    count += graph_matrix[k][i][j];
                sum_matrix[i][j] = count;   
            }
       
        /* cycle detection */
        cycled_vertices_num = 0;
        good_vertices_num = 0;
        for (i=0; i<cities; i++) {
            if (sum_matrix[i][i]>0) {
               cycled_vertices[cycled_vertices_num] = i;
               cycled_vertices_num++;                     
            } else {
               good_vertices[good_vertices_num] = i;
               good_vertices_num++;                     
            }
        }
       
        /*  replacing all values for accessible vertices of cycled vertices with -1 */
        for (i=0; i<cycled_vertices_num; i++) {
            k = cycled_vertices[i];
            for (j=0; j<cities; j++)
                if (sum_matrix[k][j]>0)
                   sum_matrix[k][j] = -1;   
        }
       
        /* scanning good vertices, if good vertex has a route to a cycled vertice, all accessible points for this cycled vertice
           must be replaced with -1 in good vertex */
        for (i=0; i<good_vertices_num; i++) {
            k = good_vertices[i];
            for (j=0; j<cities; j++) {
                if (sum_matrix[k][j] > 0 && sum_matrix[j][j] < 0) {
                   for (c=0; c<cities; c++)
                       if (sum_matrix[j][c] < 0)
                          sum_matrix[k][c] = -1;                     
                }
            }   
        }
       
        printf ("matrix for city %d\n", case_no);
        for (i=0; i<cities; i++) {
            for (j=0; j<cities; j++) {
                if (j != 0)
                   printf(" ");
                printf ("%d", sum_matrix[i][j]);
            }
            printf ("\n");   
        }
                     
     } else
       break;             
  }
 
  return 0;
}



Maybe the problem lies in invalid input handling?