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

Общий форум

Can you tell me why I get an "WA" when I submit the T1056 problem?
Послано HateThisWebSite 18 окт 2008 17:44
I get a "WA" in the fifth test case and this is my code:
#include <iostream>
using namespace std;
const int MAXN = 10100;
struct Node{
    int parent,brother,child,depth,path;
};
Node nodes[MAXN];
int n;
void initial(){
    for(int i = 1;i<=n;i++){
        nodes[i].parent = -1;
        nodes[i].brother = -1;
        nodes[i].child = -1;
        nodes[i].depth = 1;
        nodes[i].path = -1;
    }
}
int getDepth(int p){
    int i,j,k,max = 1,path;
    if(nodes[p].child==-1) return 1;
    i = nodes[p].child;
    while(i!=-1){
        j = getDepth(i)+1;
        if(j>max){
            max = j;
            path = i;
        }
        i = nodes[i].brother;
    }
    nodes[p].depth = max;
    nodes[p].path = path;
    return max;
}
int main(){
    scanf("%d",&n);
    initial();
    int i,j,k,p,q,r,s,t;
    bool flag = false;
    for(i = 2;i<=n;i++){
        scanf("%d",&j);
        nodes[i].parent = j;
        nodes[i].brother = nodes[j].child;
        nodes[j].child = i;
    }
    i = getDepth(1);
    j = nodes[1].path;
    p = -1;
    for(k = nodes[1].child;k!=-1;p = k,k = nodes[k].brother){
        if(k==j){
            if(p==-1) nodes[1].child = nodes[k].brother;
            else{
                nodes[p].brother = nodes[k].brother;
            }
            break;
        }
    }
    k = getDepth(1);
    if((i-k)%2==1) flag = true;
    i = (i-k)/2;
    nodes[1].path = j;
    for(j = 1,k = 0;k<i;j = nodes[j].path,k++);
    if(!flag) printf("%d\n",j);
    else{
        k = nodes[j].path;
        if(k<j){
            p = k;
            k = j;
            j = p;
        }
        printf("%d %d\n",j,k);
    }

}

Thank you very much for teaching me:).