RiseOJ – 디렉터리 순회

설명

소 베시는 놀랍게도 컴퓨터를 잘 다룬다. 헛간에 있는 자신의 컴퓨터에서 베시는 소중한 파일들을 모두 디렉터리 모음에 저장해 두는데, 예를 들면 다음과 같다.

bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

bessie라는 이름의 "최상위" 디렉터리가 하나 있다.

베시는 원하는 어느 디렉터리 안으로든 이동할 수 있다. 주어진 디렉터리에서 어떤 파일이든 "상대 경로"로 참조할 수 있다. 상대 경로에서 기호 ".."는 부모 디렉터리를 가리킨다. 베시가 folder2 안에 있다면, 네 파일을 다음과 같이 참조할 수 있다.

../file1
file2
../../folder3/file3
../../file4

베시는 모든 파일에 대한 상대 경로 길이의 합이 최소가 되는 디렉터리를 선택하고 싶다.

출제자: Mark Gordon

제약

출제자: Mark Gordon

입력 형식

첫째 줄에 파일과 디렉터리의 총 개수를 나타내는 정수 N( $2 \leq N \leq 100,000$ )이 주어진다. 입력을 위해 각 객체(파일 또는 디렉터리)에는 1과 $$N$$ 사이의 고유한 정수 ID가 부여되며, ID 1은 최상위 디렉터리를 가리킨다.

다음으로 $$N$$ 개의 줄이 주어진다. 각 줄은 파일 또는 디렉터리의 이름으로 시작한다. 이름은 소문자 a-z와 숫자 0-9로만 이루어지며 길이는 최대 16이다. 이름 다음에는 정수 $$m$$ 이 주어진다. $$m$$ 이 0이면 이 객체는 파일이다. $$m > 0$$ 이면 이 객체는 디렉터리이며, 그 안에 총 $$m$$ 개의 파일 또는 디렉터리를 가진다. $$m$$ 다음에는 이 디렉터리 안에 있는 객체들의 ID를 나타내는 정수 $$m$$ 개가 주어진다.

출력 형식

모든 파일에 대한 상대 경로 길이 합의 최솟값을 출력한다. 이 값은 32비트 정수에 담기에 너무 클 수 있음에 유의하라.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 dirtraverse.in · 출력을 쓸 파일 dirtraverse.out

예제 1

입력

8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

출력

설명

This input describes the example directory structure given above.

The best solution is to be in folder1. From this directory, the relative paths
are:

file1
folder2/file2
../folder3/file3
../file4

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Gold

올림피아드 > USACO > 2017-2018 > February > Gold

태그

JudgeUSACO

디렉터리 순회

평가 및 의견

풀이 제출