아오이(Aoi)와 비타로(Bitaro)는 JOI 국가의 국가정보국에 소속된 스파이이다. 이번 그들의 임무는 IOI 국가에 대한 잠입 조사를 수행하는 것이다. 비타로는 IOI 국가로 잠입하고, 아오이는 JOI 국가에서 비타로에게 지시를 내린다.

잠입에 앞서 아오이와 비타로는 IOI 국가의 지도를 입수했다. IOI 국가에는 $0$부터 $N-1$까지 번호가 붙은 $N$개의 도시가 있다. 또한 IOI 국가에는 $0$부터 $M-1$까지 번호가 붙은 $M$개의 도로가 있다. 도로 $i$ ($0\le i\le M-1$)는 도시 $A_i$와 도시 $B_i$를 양방향으로 연결하며, 그 길이는 $C_i$이다. 몇 개의 도로를 지나면 어떤 두 도시 사이든 이동할 수 있다. 비타로는 이 도로들을 지나면서 IOI 국가의 도시들 사이를 이동한다.

추가로 $Q$개의 조사 계획이 있다. $j$번째 계획($0\le j\le Q-1$)은 IOI 국가의 도시 $T_j$를 조사하는 것이다.

위의 모든 정보는 처음에 아오이와 비타로 모두에게 주어졌다. 그 후 비타로는 IOI 국가로의 잠입을 진행했다.

비타로는 수많은 추격자를 따돌리고 암살자들을 물리친 끝에, 마침내 IOI 국가의 도시 $0$에 잠입하는 데 성공했다. 하지만 잠입 작전이 극도로 어려웠던 탓에, 비타로는 IOI 국가에 대한 일부 정보를 잃어버렸다. 구체적으로 비타로는 $K$개의 도로, 즉 도로 $X_0,X_1,\ldots,X_{K-1}$의 길이에 대한 정보를 잃어버렸다. 다시 말해, 비타로는 더 이상 $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$의 값을 알지 못한다. 비타로는 이 정보를 잃어버렸지만, 아오이는 여전히 이를 보유하고 있다는 점에 유의하라.

비타로는 즉시 자신이 어떤 도로의 길이 정보를 잃어버렸는지 아오이에게 보고했다.

임무를 완수하기 위해, 비타로는 도시 $0$에서 $Q$개의 조사 계획의 목표가 되는 각 도시까지의 최단 경로를 알고 싶어 한다.

아오이는 비타로를 돕기 위해 각 문자가 0 또는 1인 문자열을 보낼 것이다. 도청의 위험 때문에 아오이는 비타로에게 보내는 내용을 최소화하고 싶어 한다.

IOI 국가에 대한 정보, 조사 계획, 그리고 비타로가 정보를 잃어버린 도로들이 주어졌을 때, 비타로에게 문자열을 보내는 아오이의 전략을 구현하는 프로그램을 작성하라. 또한, 비타로가 가지고 있는 정보와 아오이가 보낸 문자열이 주어졌을 때, 최단 경로를 찾는 비타로의 전략을 구현하는 프로그램을 작성하라.

구현 세부 사항

여러분은 2개의 파일을 제출해야 한다.

첫 번째 파일은 Aoi.cpp이다. 이 파일은 아오이의 전략을 구현하기 위한 것이며 다음 함수를 구현해야 한다. 프로그램은 전처리기 지시자 #include를 사용하여 Aoi.h를 포함해야 한다.

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X)

이 함수는 각 테스트 케이스마다 단 한 번 호출된다.

• 매개변수 N은 IOI 왕국의 도시의 수 $N$이다.
• 매개변수 M은 IOI 왕국의 도로의 수 $M$이다.
• 매개변수 Q는 조사 계획의 수 $Q$이다.
• 매개변수 K는 비타로가 길이 정보를 잃어버린 도로의 수 $K$이다.
• 매개변수 A, B, C는 길이가 $M$인 배열이다. 이는 도로 $i$ ($0\le i\le M-1$)가 도시 A[i]와 도시 B[i]를 양방향으로 연결하며, 그 길이가 C[i]임을 의미한다.
• 매개변수 T는 길이가 $Q$인 배열이다. 이는 $j$번째 계획($0\le j\le Q-1$)이 도시 T[j]를 조사하는 것임을 의미한다.
• 매개변수 X는 길이가 $K$인 배열이다. 이는 비타로가 도로 X[0], X[1], ..., X[K-1]의 길이 정보를 잃어버렸음을 나타낸다.
• 반환값은 아오이가 비타로에게 보내는 문자열 $s$이다.
• 문자열 $s$의 각 문자는 0 또는 1이어야 한다. 이 조건이 충족되지 않으면 프로그램은 Wrong Answer [1]로 판정된다.
• 문자열 $s$의 길이는 최대 $12\,000$이어야 한다. 이 조건이 충족되지 않으면 프로그램은 Wrong Answer [2]로 판정된다.

두 번째 파일은 Bitaro.cpp이다. 이 파일은 비타로의 전략을 구현하기 위한 것이며 다음 함수를 구현해야 한다. 프로그램은 전처리기 지시자 #include를 사용하여 Bitaro.h를 포함해야 한다.

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s)

이 함수는 aoi 함수가 호출된 후 단 한 번 호출된다.

• 매개변수 N은 IOI 왕국의 도시의 수 $N$이다.
• 매개변수 M은 IOI 왕국의 도로의 수 $M$이다.
• 매개변수 Q는 조사 계획의 수 $Q$이다.
• 매개변수 K는 비타로가 길이 정보를 잃어버린 도로의 수 $K$이다.
• 매개변수 A, B, C는 길이가 $M$인 배열이다. 이는 도로 $i$ ($0\le i\le M-1$)가 도시 A[i]와 도시 B[i]를 양방향으로 연결하며, 그 길이가 C[i]임을 의미한다.
• 매개변수 T는 길이가 $Q$인 배열이다. 이는 $j$번째 계획($0\le j\le Q-1$)이 도시 T[j]를 조사하는 것임을 의미한다.
• 매개변수 X는 길이가 $K$인 배열이다. 이는 비타로가 도로 X[0], X[1], ..., X[K-1]의 길이 정보를 잃어버렸음을 나타낸다.
• 인자 s는 각 문자가 0 또는 1인 문자열로, 아오이가 비타로에게 보낸 문자열을 나타낸다.

Bitaro.cpp 내에서 프로그램은 다음 함수를 호출할 수 있다.

void answer(const std::vector<int> &e)

이 함수의 $(j+1)$번째 호출($0\le j\le Q-1$)에서, 여러분은 $j$번째 조사 계획의 목표인 도시 $0$에서 도시 $T_j$까지의 최단 경로를 답해야 한다.

• 매개변수 e는 도시 $0$에서 도시 $T_j$까지의 최단 경로를 나타내는 배열이다.
• 배열 e의 길이를 $n$이라고 하자. 원소 e[0], e[1], ..., e[n-1]은 도시 $0$에서 도시 $T_j$까지의 최단 경로에 있는 도로들의 인덱스이며, 이동하는 순서대로 나열된다.
• 가능한 최단 경로가 여러 개 있다면, 그중 어느 것을 답으로 선택해도 된다.
• 매개변수 e의 각 원소는 $0$ 이상 $M-1$ 이하여야 한다. 이 조건이 충족되지 않으면 프로그램은 Wrong Answer [3]으로 판정된다.

• 인자 e가 나타내는 도로들의 열은 도시 $0$에서 도시 $T_j$까지의 경로를 형성해야 한다. 보다 엄밀하게는 다음 조건을 만족해야 한다.

  다음과 같은 수열 $u_0,u_1,\ldots,u_n$이 존재한다:

  • $u_0=0$.
  • $u_n=T_j$.
  • 도로 e[k] ($0\le k\le n-1$)는 도시 $u_k$와 도시 $u_{k+1}$을 연결한다.

  이 조건들이 충족되지 않으면 프로그램은 Wrong Answer [4]로 판정된다.

• 인자 e가 나타내는 도로들의 열이 도시 $0$에서 시작하여 도시 $T_j$에서 끝나는 모든 경로 중 도시 $0$에서 도시 $T_j$까지의 최단 경로가 아니라면, 프로그램은 Wrong Answer [5]로 판정된다. 여기서 경로의 길이는 사용된 도로들의 길이의 합으로 정의된다.

• answer 함수는 정확히 $Q$번 호출되어야 한다. bitaro 함수의 실행이 끝났을 때 answer 함수의 호출 횟수가 $Q$와 같지 않다면, 프로그램은 Wrong Answer [6]으로 판정된다.

중요 공지

• 프로그램은 내부 사용을 위해 다른 함수를 구현하거나 전역 변수를 사용할 수 있다. 제출된 파일들은 채점기(grader)와 함께 컴파일되어 단일 실행 파일이 된다. 다른 파일과의 충돌을 피하기 위해 모든 전역 변수와 내부 함수는 이름 없는 네임스페이스(unnamed namespace) 안에 선언되어야 한다. 채점 시에는 아오이와 비타로의 두 프로세스로 실행된다. 아오이의 프로세스와 비타로의 프로세스는 전역 변수를 공유할 수 없다.
• 프로그램은 표준 입력과 표준 출력을 사용해서는 안 된다. 프로그램은 어떠한 방법으로도 다른 파일과 통신해서는 안 된다. 단, 표준 에러(standard error)로 디버깅 정보를 출력하는 것은 허용된다.

컴파일 및 테스트 실행

대회 웹페이지에서 프로그램을 테스트하기 위한 샘플 채점기가 포함된 아카이브 파일을 다운로드할 수 있다. 이 아카이브 파일에는 프로그램의 샘플 소스 파일도 포함되어 있다.

샘플 채점기는 grader.cpp 파일이다. 프로그램을 테스트하려면 grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h를 같은 디렉터리에 두고 다음 명령을 실행하여 프로그램을 컴파일하라. 대신 아카이브 파일에 포함된 compile.sh를 실행해도 된다.

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

컴파일에 성공하면 실행 파일 grader가 생성된다.

실제 채점기는 샘플 채점기와 다르다는 점에 유의하라. 샘플 채점기는 단일 프로세스로 실행되며, 표준 입력으로부터 입력 데이터를 읽고 그 결과를 표준 출력과 표준 에러 출력에 기록한다.

샘플 채점기의 입력

샘플 채점기는 표준 입력으로부터 다음 데이터를 읽어들인다.

$$ \begin{gathered} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{gathered} $$

샘플 채점기의 출력

샘플 채점기는 표준 출력과 표준 에러 출력에 다음 정보를 출력한다(명확성을 위해 따옴표로 표기).

• 프로그램이 Wrong Answer [1], [2], [3], [4], 또는 [6]으로 판정되면, 샘플 채점기는 표준 에러 출력에 그 종류를 Wrong Answer [1]과 같이 기록한다. 표준 출력에는 아무것도 출력되지 않는다.
• 그렇지 않다면, aoi 함수로부터 반환된 문자열 $s$의 길이가 Accepted: 2024 형식으로 표준 에러 출력에 출력된다. 추가로, answer 함수의 $(j+1)$번째 호출($0\le j\le Q-1$)에서의 경로의 길이가 표준 출력의 $(j+1)$번째 줄에 출력된다. 샘플 채점 프로그램은 그 경로가 최단 경로인지 여부는 검사하지 않는다.

프로그램이 여러 종류의 Wrong Answer 조건을 동시에 만족하는 경우, 샘플 채점기는 그중 하나만 보고한다.

제한

모든 입력 데이터는 다음 조건을 만족한다:

• $2\le N\le10\,000$.
• $1\le M\le20\,000$.
• $1\le Q\le16$.
• $1\le K\le300$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le M-1$).
• $(A_i,B_i)\ne(A_j,B_j)$ ($0\le i<j\le M-1$).
• $1\le C_i\le10^{12}$ ($0\le i\le M-1$).
• $1\le T_j\le N-1$ ($0\le j\le Q-1$).
• $T_j\ne T_k$ ($0\le j<k\le Q-1$).
• $0\le X_k\le M-1$ ($0\le k\le K-1$).
• $X_k\ne X_l$ ($0\le k<l\le K-1$).
• 몇 개의 도로를 지나면 어떤 도시에서 다른 어떤 도시로든 이동할 수 있다.
• 모든 입력 값은 정수이다.

채점 기준

어느 테스트 케이스에서든 프로그램이 Wrong Answer [1]–[6](구현 세부 사항 참조) 중 하나로 판정되거나 런타임 에러(TLE(시간 초과), MLE(메모리 초과), 비정상 종료 등)가 발생하면, 점수는 $0$점이다.

그렇지 않다면, 채점은 이 과제의 모든 테스트 케이스에 걸쳐 aoi 함수가 반환한 문자열 $s$의 최대 길이 $L$을 기준으로 이루어진다.

• $1561\le L\le12\,000$이면, 점수는 $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$점이다.
• $0\le L\le1560$이면, 점수는 $100$점이다.

여기서 $\lfloor x\rfloor$는 $x$보다 크지 않은 가장 큰 정수를 나타낸다.

예제

다음은 샘플 채점기를 위한 예제 입력과 이에 대응하는 함수 호출이다.

입력 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

함수 호출 예제

도시 $0$에서 도시 $1$까지의 최단 경로는 도로 $1$과 $0$을 이 순서대로 지나거나, 단순히 도로 $2$를 지나는 것으로 달성된다. 따라서 이 예제에서 answer 함수의 두 번째 호출에 대해서는 answer([2])를 호출하는 것도 허용된다.

대회 사이트에서 다운로드할 수 있는 파일 sample-01-in.txt는 입력 예제 1에 해당한다.

대회 사이트에서 다운로드 가능한 파일들에 포함된 sample-01-in.txt와 sample-02-in.txt는 샘플 채점기의 입력으로 사용할 수 있다.