0
Your rating: None

CodeChef submission 509539 (C++ 4.3.2)

CodeChef submission 509539 (C++ 4.3.2) plaintext list. Status: WA, problem MUFFINS, contest . By opethgeek (opethgeek), 2011-04-07 11:51:01.
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int countPossible(int **c, int m, int *cnt, int **mat, int n)
  5. {
  6.   int i, j,k;
  7.   int min, mi;
  8.   int count = 0, conf = 0;
  9.   int *cnt2, x;
  10.  
  11.   cnt2 = (int *)malloc(sizeof(int) * n);
  12.   
  13.   for(i = 0; i < n; i++)
  14.     cnt2[i] = cnt[i];
  15.  
  16.   for(i = 0; i < n; i++){
  17.     min = 100000;
  18.     for(j = 0; j < n; j++){
  19.       if(cnt[j] < min && cnt > 0){
  20. 	min = cnt[j];
  21. 	mi = j;
  22.       }
  23.     }
  24.  
  25.     conf = 0;
  26.     for(j = 0; j < cnt[mi]; j++)
  27.       if(mat[mi][j] == -1)
  28. 	conf = 1;
  29.  
  30.     if(!conf)
  31.       for(j = 0; j < n; j++){
  32. 	if(cnt[j] != 1000000)
  33. 	  for(k = 0; k < cnt[j]; k++){
  34. 	    if(mat[j][k] == mi)
  35. 	      mat[j][k] = -1;
  36. 	  }
  37.  
  38.       }
  39.     cnt[mi] = 1000000;
  40.  
  41.   }
  42.  
  43.   for(i = 0; i < n; i++){
  44.     conf = 0;
  45.     for(j = 0; j < cnt2[i]; j++)
  46.       if(mat[i][j] == -1) conf = 1;
  47.     if(!conf) count++;
  48.   }
  49.  
  50.   return count;
  51. }
  52.  
  53.  
  54. main()
  55. {
  56.   int i, j, p, count;
  57.   int n, m, g, gprime;
  58.   int **c;
  59.   int **mat;
  60.   int *cnt;
  61.   int *conflicting;
  62.   int x;
  63.  
  64.  
  65.   scanf("%d", &p);
  66.  
  67.   for(i = 0; i < p; i++){
  68.  
  69.     scanf("%d %d %d", &n, &m, &g);
  70.     c = (int **)malloc(sizeof(int *) * m);
  71.     for(j = 0; j < m; j++)
  72.       c[j] = (int *)malloc(sizeof(int) * 2);
  73.     cnt = (int *)malloc(sizeof(int) * n);
  74.     conflicting = (int *)malloc(sizeof(int) * n);
  75.     mat = (int **)malloc(sizeof(int *) * n);
  76.     
  77.     for(j = 0; j < n; j++)
  78.       conflicting[j] = cnt[j] = 0;
  79.     for(j = 0; j < m; j++){
  80.       scanf("%d %d", &c[j][0], &c[j][1]);
  81.       cnt[c[j][0]]++;
  82.       cnt[c[j][1]]++;
  83.       conflicting[c[j][0]] = conflicting[c[j][1]] = 1;
  84.     }
  85.     x = -10000;
  86.     for(j = 0; j < n; j++)
  87.       if(cnt[j] > x) x = cnt[j];
  88.  
  89.     
  90.     for(j = 0; j < n; j++){
  91.       mat[j] = (int *) malloc(sizeof(int) * x);
  92.       cnt[j] = 0;
  93.     }
  94.     
  95.     for(j = 0; j < m; j++){
  96.       mat[c[j][0]][cnt[c[j][0]]] = c[j][1];
  97.       mat[c[j][1]][cnt[c[j][1]]] = c[j][0];
  98.       cnt[c[j][0]]++;
  99.       cnt[c[j][1]]++;
  100.     }
  101.  
  102.     gprime = 0;
  103.     for(j = 0; j < n; j++)
  104.       count += !conflicting[j];
  105.  
  106.     // reduce g by the number of spaces that have no conflict
  107.     g -= count;
  108.     if(countPossible(c,m,cnt,mat,n) < g)
  109.       printf("Impossible\n");
  110.     else
  111.       printf("Possible\n");
  112.  
  113.   }
  114. }
  115.

Comments