시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 2184 | 861 | 618 | 43.277% |
그래프 G는 정점의 집합 V와 간선의 집합 E로 이루어져 있고, G = (V, E)로 나타낸다. 대부분의 경우에 V와 E는 명시되어 있다. 일부 그래프의 경우에는 집합이 명시되어 있지 않다. 예를 들어, 순열 그래프는 간선의 집합이 명시되어 있지 않다.
{1, 2, 3, 4, 5}로 이루어진 두 순열 (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)가 있다. 평행선을 그리고, 그 위에 순열에 적힌 숫자 순서대로 정점을 그린다. 그 다음 같은 숫자끼리 선분을 연결한다. 아래 그림과 같이 교차하는 선분의 쌍은 총 여섯 개라는 것을 알 수 있다.
교차하는 쌍은 순열 그래프의 간선이 된다. 순열 그래프의 정점은 숫자가 되고, 간선은 교차하는 쌍이 된다. 위의 예를 이용해 순열 그래프를 만들면 V = {1, 2, 3, 4, 5}, E = {(1,2), (1,4), (1,5), (2,3), (2,5), (3,4)}. 위의 두 순열을 이용해 순열 그래프를 그리면 아래 그림과 같이 된다.
{1, 2, ..., n}으로 이루어진 두 순열이 주어졌을 때, 두 순열을 이용해 만든 순열 그래프의 간선의 개수를 구하는 프로그램을 작성하시오. 예를 들어, (2, 5, 4, 1, 3)과 (1, 5, 3, 2, 4)로 만든 순열 그래프의 간선의 개수는 6개이다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. 둘째 줄과 셋째 줄에는 두 순열이 주어진다. 순열은 {1, 2, ..., n}으로 이루어져 있고, 공백으로 구분되어져 있다. (1 ≤ n ≤ 100,000)
각 테스트 케이스 마다, 입력으로 주어진 두 순열로 만든 순열 그래프의 간선의 개수를 출력한다.
3 5 2 5 4 1 3 1 5 3 2 4 7 5 6 7 1 2 3 4 5 6 7 1 2 3 4 7 1 5 3 4 2 7 6 7 1 5 3 4 2 6
6 0 5
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2013 I번