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

Обсуждение задачи 1281. River Basin

Some clarifications (+)
Послано Michael Rybak (accepted@ukr.net) 6 фев 2006 02:42
//
below, when speaking about broken lines, for any line I divide it's points into endpoints (first and last) and inner points (the rest)
//

I had the following 4 questions when solving this problem:

1. Is "tributarity" transitive? I.e. when calculating basin area, do we only consider the river and it's tributaries, or do we also look at tributaries' tributaries, and tributaries of those tributaries etc?

2. Is it assumed that points in the river are ordered from head to mouth (or from head to entry-to-parent-river)?

3. Is it true that a river A is a tributary of river B if and only if one of endpoints of A is an inner point (not endpoint!) of B?

4. Can an inner vertex be a turning point and an entry point  of a tributary flow at the same time (or tributaries only enter in points which lie on some straight part of the broken line - like in problem samples)?

I did the following assumptions and got AC, so either they are right or there's no testdata to distinguish:

1. Yes, we include all the hierarchy
2. No, any endpoint may be an entry to a "parent" river. But not both - one of 2 endpoints is always head (as problem statement says)
 NOTE: this is only my (maybe false) assumption that complicates things just a bit, and doesn't contradict the opposite assumption, but covers it instead.
3. Yes.
4. Yes. All inner points can be subflows' entry points.

P.S. In fact, question 2 is almost unnecesary because problem statement says: "Every river is shown as a broken line, which begins with a river head and ends either at the point where the river flows into another one, or on the river mouth". The problematic word here is "shown". Is it equal to "given in input file?", i.e. does this order correspond to input data?

Edited by author 06.02.2006 02:44

Edited by author 06.02.2006 02:46