Блог пользователя NekoKarp

Автор NekoKarp, история, 6 лет назад, По-русски

Есть такая задача: дано подвешенное дерево и запросы к нему. Каждый запрос — путь в графе, причём LCA концов границ этого отрезка — одна из этих границ. В каждой вершине написано число от 0 до n. Для каждого запроса в порядке их поступления требуется идя по нему от 1 границы до другой занулить все вершины, которые равны n, исключая края отрезков таких вершин. Иными словами, если на этом пути встречаются несколько подряд идущих вершин равных n, то с первой и последней из них мы ничего не делаем, а остальным присваиваем 0. Я предполагаю, что данную задачу можно решить сканлайном вида "будем обходить дерево DFS-ом и заходя в вершину, из которой начинается отрезок начинаем занулять, проверяя не конец ли текущая вершина", но по неизвестным причинам такой способ получает WA(вероятно из-за порядка запросов, а он, как видно из условия, важен), был бы рад, если бы кто-нибудь поможет с этой задачей. Желательно предоставить конкретную реализацию или доказательство, что моя идея ошибочна.

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Сложно написать стресс тест?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -30 Проголосовать: не нравится

    Проблема не в том, чтобы понять, на каких тестах ошибка, а в том, почему она возникает с иденой точки зрения

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Зная небольшой тест, несложно понять, в чем ошибка

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится -31 Проголосовать: не нравится

        Ключевое слово небольшой. Когда ошибка возникает при размере графа 10^5+ это сомнительная тактика