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

Обсуждение задачи 1182. Team Them Up!

Who Can Help ME?
Послано davidsun 5 мар 2007 17:49
WA On Test #16

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

#define max(a, b) (a) > (b) ? (a) : (b)

bool link[101][101];
int n;

int main(void){
    memset(link, false, sizeof(link));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        int next; scanf("%d", &next);
        while (next != 0){
              link[i][next] = true;
              scanf("%d", &next);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (!link[i][j] || !link[j][i]){
               link[i][j] = link[j][i] = true;
            }  else {
               link[i][j] = link[j][i] = false;
            }
        }
    }

    bool vis[101]; memset(vis, false, sizeof(vis));
    int blocks[101][101][2], blocks_size[101][2], blocks_count = -1;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){  //???????????
            if (link[i][j] && !vis[i]){
               int queue[2][101], queue_size[2], head[2];
               queue_size[0] = queue_size[1] = 0;
               head[0] = head[1] = 0;
               queue[1][0] = i; vis[i] = true;
               queue[0][0] = j; vis[j] = true;
               while (head[0] <= queue_size[0] || head[1] <= queue_size[1]){
                     if (head[0] <= queue_size[0]){
                        int point = queue[0][head[0]];
                        for (int k = 1; k <= n; k++){
                            if (link[point][k] && !vis[k]){
                               queue[1][++queue_size[1]] = k;
                               vis[k] = true;
                            }
                        }
                        head[0]++;
                     }

                     if (head[1] <= queue_size[1]){
                        int point = queue[1][head[1]];
                        for (int k = 1; k <= n; k++){
                            if (link[point][k] && !vis[k]){
                               queue[0][++queue_size[0]] = k;
                               vis[k] = true;
                            }
                        }
                        head[1]++;
                     }
               }

               for (int k = 0; k <= queue_size[0]; k++){
                   for (int l = k + 1; l <= queue_size[0]; l++){
                       if (link[queue[0][k]][queue[0][l]]){
                          printf("No solution\n");
                          getchar(); getchar(); getchar(); getchar();
                          return 0;
                       }
                   }
               }

               for (int k = 0; k <= queue_size[1]; k++){
                   for (int l = k + 1; l <= queue_size[1]; l++){
                       if (link[queue[1][k]][queue[1][l]]){
                          printf("No solution\n");
                          getchar(); getchar(); getchar(); getchar();
                          return 0;
                       }
                   }
               }

               blocks_count++;
               blocks_size[blocks_count][0] = queue_size[0];
               blocks_size[blocks_count][1] = queue_size[1];
               for (int k = 0; k <= queue_size[0]; k++) blocks[blocks_count][k][0] = queue[0][k];
               for (int k = 0; k <= queue_size[1]; k++) blocks[blocks_count][k][1] = queue[1][k];
            }
        }
    }

    for (int i = 1; i <= n; i++){
        if (!vis[i]){
           blocks_count++;
           blocks_size[blocks_count][0] = 0;
           blocks_size[blocks_count][1] = -1;
           blocks[blocks_count][0][0] = i;
           vis[i] = true;
        }
    }

    bool status[101], status_x[101];
    bool way[101][101], way_x[101][101];
    memset(way, false, sizeof(way));
    memset(status, false, sizeof(status));
    status[0] = true;
    for (int i = 0; i <= blocks_count; i++){
        memset(way_x, false, sizeof(way_x));
        memset(status_x, false, sizeof(status_x));
        for (int j = 0; j <= n / 2; j++){
            if (status[j]){
               if (!status_x[j + blocks_size[i][0] + 1] && j + blocks_size[i][0] + 1 <= n / 2){
                     status_x[j + blocks_size[i][0] + 1] = true;
                  memcpy(way_x[j + blocks_size[i][0] + 1], way[j], sizeof(way_x[j + blocks_size[i][0] + 1]));
                     for (int k = 0; k <= blocks_size[i][0]; k++){
                            way_x[j + blocks_size[i][0] + 1][blocks[i][k][0]] = true;
                  }
               }

               if (!status_x[j + blocks_size[i][1] + 1] && j + blocks_size[i][1] + 1 <= n / 2){
                     status_x[j + blocks_size[i][1] + 1] = true;
                  memcpy(way_x[j + blocks_size[i][1] + 1], way[j], sizeof(way_x[j + blocks_size[i][1] + 1]));
                     for (int k = 0; k <= blocks_size[k][1]; k++){
                            way_x[j + blocks_size[i][1] + 1][blocks[i][k][1]] = true;
                     }
               }
            }
        }
        memcpy(way, way_x, sizeof(way_x));
        memcpy(status, status_x, sizeof(status_x));
    }

    for (int i = n / 2; i >= 1; i--){
        if (status[i]){
           printf("%d", i);
           for (int j = 1; j <= n; j++){
                  if (way[i][j]) printf(" %d", j);
           }

           printf("\n%d", n - i);
           for (int j = 1; j <= n; j++){
                  if (!way[i][j]) printf(" %d", j);
           }
        }

        break;
    }

    getchar(); getchar(); getchar(); getchar();
}
Re: Who Can Help ME?
Послано davidsun 6 мар 2007 15:26
Sorry, I've made some silly mistakes. I'll try to do better next time. Thanks!