Помогите решить задачу EOlimp

Question

Итак, вот сама задача: https://www.eolymp.com/ru/problems/3922

Вот мое решение на, скажем, псевдокоде:

function solve(input: string) -> string {
    let lines = input.split("\n");
    let n = int(lines[0]);
    
    let l = lines.length();
    for(let j = 0; j < lines.length(); j += 1) {
        if(lines[j].length() == 0) { l -= 1; }   
    }
    
    let mes: int[] = [];
    let pos: int[] = [];
    let i = 1;
    while(i < l) {
        mes.push(int(lines[i]));
        pos.push(i);
        if(int(lines[i]) == 0) { i += 3;}
        else { i += 2;}
    }
    
    let rel: int[] = [];
    for(let j = 0; j < mes.length(); j += 1) {
        rel.push(0);
    }
    
    for(let j = 0; j < mes.length(); j += 1) {
        if(mes[j] != 0) {
            if(mes[mes[j] - 1] == 0) {
                rel[mes[j] - 1] += 1;
            }
        }
    }
    
    let index = 0;
    for(let j = 0; j < rel.length(); j += 1) {
        if(rel[j] > rel[index]) {
            index = j;
        }
    }
    
    
    return lines[pos[index] + 1];
}

input здесь - строка входных данных (естественно с символами перевода курсора \n), ответ выводится в return. На сэмплах у меня работает, но при отправке хватаю WA. Возможно, я что-то где-то упускаю. Подскажите пожалуйста, где?)

Answer 1

Просто идем с конца и добавляем счетчик к тому, на которое данное сообщение является ответом. Потом ищем максимальный счетчик среди нулей.

Собственно, всё. Никаких деревьев...

struct Msg
{
    int no;
    string subj;
    string text;
    int    count = 0;
};

int main()
{
    int n;
    cin >> n;
    vector<Msg> m;
    for(int i = 0; i < n; ++i)
    {
        Msg s;
        cin >> s.no; cin.ignore(1000,'\n');
        if (s.no == 0) getline(cin,s.subj);
        getline(cin,s.text);
        m.push_back(s);
    }
    for(size_t i = m.size(); i-->0; )
    {
        m[i].count++;
        if (m[i].no) m[m[i].no-1].count += m[i].count;
    }

    auto it = *max_element(m.begin(),m.end(),
                           [](const Msg& a, const Msg& b)
                           {
                               if (a.no > b.no) return true;
                               if (a.no < b.no) return false;
                               return a.count < b.count;
                           });
    cout << it.subj;
}

БЛОГ НА HUSL

Помогите решить задачу EOlimp

Ответы (1 шт):