Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.03.2009, 12:24
гость

 
Сообщений: n/a

задача 398
Wrong answer on test 42. Если кто решал помогите разобраться.

#include <stdio.h>
#include <iostream>

bool in_array(int a[], int size, int value)
{
int count=0;
for (int i=0; i<size; i++)
if (a[i]==value)
return true;
return false;
}

int sort(int a[], int size)
{
int temp;
int realsize=size;
for (int i=0;i<size-1;i++)
if (a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
for (int i=0;i<size-1;i++)
for (int j=i+1;j<size;j++)
{
if (a[i]==a[j] && a[j]!=0)
{
a[j]=0;
realsize--;
}
}
return realsize;
}
int main()
{
int friends[50][51];
int xfriends[50];
int xfriendsfriends[2500];
int man_count, x;
std::cin>>man_count;
std::cin>>x;
int row=0;
for (int j=0;j<man_count;j++)
{
std::cin>>friends[row][0];
for (int k=1;k<=friends[row][0];k++)
std::cin>>friends[row][k];
row++;
}
if (friends[x-1][0])
{
for (int i=1; i<=friends[x-1][0];i++)
xfriends[i-1]=friends[x-1][i];
int frfrcount=0;
for (int i=0; i<friends[x-1][0];i++)
{
for (int j=1;j<=friends[xfriends[i]-1][0];j++)
if (friends[xfriends[i]-1][j]!=x && !in_array(xfriends,friends[x-1][0],friends[xfriends[i]-1][j]))
{
xfriendsfriends[frfrcount]=friends[xfriends[i]-1][j];
frfrcount++;
}
}
int realsize=sort(xfriendsfriends,frfrcount);
std::cout<<realsize;
if (realsize)
std::cout<<"\n";
{
int count=realsize;
for (int i=0; i<frfrcount;i++)
{
if (xfriendsfriends[i] && count>1)
{
std::cout<<xfriendsfriends[i]<<" ";
count--;
continue;
}
if (xfriendsfriends[i] && count==1)
{
std::cout<<xfriendsfriends[i];
count--;
}
}
}
}
else
std::cout<<0;
return 0;
}
  #2  
Старый 08.03.2009, 15:25
гость

 
Сообщений: n/a

Блин, но какой у вас ужасный код... Раз уже пишите на C++, то научитесь пользоваться STL - это сэкономит кучу времени, код будет короче, понятнее и с меньшим числом багов. Например сортирка делается функцией std::sort, нечего изобретать велосипед, который у вас и так сломан.
  #3  
Старый 08.03.2009, 15:28
гость

 
Сообщений: n/a

Удаление дубликатов из массива - std::unique (или, как вариант, можно все числа добавлять в std::set, а в конце пройтись по нему итератором)

Цитата:
std::cout<<realsize;
if (realsize)
std::cout<<"\n";
Видимо, вы не в курсе - в конце каждой строки текстого файла, включая последную, должен присутствовать символ \n.
acm.sgu.ru вам прощает отсутствие \n в конце последней строки, но вообще это неправильно.
  #4  
Старый 08.03.2009, 23:25
гость

 
Сообщений: n/a

Всем спасибо, тест пройден
  #5  
Старый 27.10.2009, 20:52
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

Подскажите, пожалуйста, в чем тут ошибка (WA 13)

Код:
#include <cstdio>
#include <memory.h>
#include <vector>
#include <algorithm>

using namespace std;

#define maxn 100

vector < vector <int> > g (maxn);
vector <int> friends;
int n, x, u[maxn], f[maxn];

void dfs(int v) {
  u[v] = 1;
  for (int i = 0; i < g[v].size(); i++)
    if (!u[g[v][i]]) {
      if (!f[g[v][i]]) {
        friends.push_back(g[v][i]);
        f[g[v][i]] = 1;
      }
      dfs(g[v][i]);
    }
}

int main() {
  scanf("%d %d", &n, &x);
  for (int i = 1; i <= n; i++) {
    int d, v;
    scanf("%d", &d);
    for (int j = 0; j < d; j++) {
      scanf("%d", &v);
      g[i].push_back(v);
      g[v].push_back(i);
    }
  }
  
  memset(u, 0, sizeof(u));
  memset(f, 0, sizeof(f));
  
  for (int i = 0; i < g[x].size(); i++)
    f[g[x][i]] = 1;
  f[x] = 1;
  
  for (int i = 0; i < g[x].size(); i++)
    if (!u[g[x][i]])
      dfs(g[x][i]);
      
  sort(friends.begin(), friends.end());
  printf("%d\n", friends.size());
  for (int i = 0; i < friends.size(); i++)
    printf("%d ", friends[i]);
  printf("\n");
}
__________________
Irreparabilium felix oblivio rerrum.
  #6  
Старый 09.11.2009, 06:42
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

Заменил dfs на bfs, друзья друзей == те, до которых расстояние 2. ac.

Код:
#include <cstdio>
#include <memory.h>
#include <vector>
#include <queue>

using namespace std;

#define maxn 100

vector < vector <int> > g (maxn);
queue <int> q;
int n, x, u[maxn], d[maxn];

void bfs(int v) {
  q.push(v); u[v] = 1;
  while (!q.empty()) {
    v = q.front(); q.pop();
    for (int i = 0; i < g[v].size(); i++)
      if (!u[g[v][i]]) {
        q.push(g[v][i]);
        d[g[v][i]] = d[v] + 1;
        u[g[v][i]] = 1;
      }
  }
}

int main() {
  scanf("%d %d", &n, &x);
  for (int i = 1; i <= n; i++) {
    int d, v;
    scanf("%d", &d);
    for (int j = 0; j < d; j++) {
      scanf("%d", &v);
      g[i].push_back(v);
      g[v].push_back(i);
    }
  }
  
  memset(u, 0, sizeof(u));
  memset(d, 0, sizeof(d));
  
  bfs(x);

  int c = 0;
  for (int i = 1; i <= n; i++)
    c += (d[i] == 2);

  printf("%d\n", c);
  for (int i = 1; i <= n; i++)
    if (d[i] == 2)
      printf("%d ", i);
  printf("\n");
}
__________________
Irreparabilium felix oblivio rerrum.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра