[2021 SCPC 1차 예선]

차이

\(N\)개의 변수 \(X_1.,X_2,…,X_N\)이 있다. 처음에는 \(X_i\)들의 값에 대한 어떤 정보도 가지고 있지 않다. \(K\)개의 명령이 주어지는데, 명령은 두가지 종류이다. 첫번째 종류는 두 변수의 차이를 알려주는 것이다. 즉, \(X_i-X_j=d\)라는 정보를 준다. \(X_j-X_i=-d\)라는 정보도 주어진 것으로 간주한다. 두번째 종류는 두 변수의 차이를 묻는 것이다. 명령들은 하나하나 순서대로 주어지는 것으로 생각한다.



두번째 종류의 명령에 대한 대답은 다음의 3가지가 있다.



    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이가 유일하게 정해지면 그 값을 출력해야 한다.

    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 방법이 전혀 없다면 NC를 출력한다. NC의 의미는 Not Connected이다.

    - 그 시점까지 주어진 모든 정보에 따라 두 변수의 차이를 유추할 수 있지만 하나로 정하는 것이 불가능하다면 CF를 출력한다. CF의 의미는 Conflict이다.



위의 조건을 자세히 설명하면 다음과 같다: 두번째 종류의 명령에서 주어진 두 변수를 \(X_i\)와 \(X_j\)라고 하자. \(X_i\)에서 \(X_j\)로의 연결은 변수의 열인데, 처음이 \(X_i\)이고 마지막이 \(X_j\)이며 열에서 인접한 모든 쌍이 그 시점까지 첫번째 종류의 명령으로 주어진 것이라야 한다. 인접한 쌍이 첫번째 종류의 명령에서 등장한 순서대로일 필요는 없다. \(X_i\)에서 \(X_j\)로의 연결은 여러 개가 존재할 수 있음에 주의하라. \(X_i\)에서 \(X_j\)로의 연결을 따라 계산한다는 것은 다음과 같이 정의된다. \([X_i,X_k,…,X_j]\)가 연결이라고 하자. \(X_i- X_k\)의 값에 대한 정보가 여러 번 주어진 경우 어떤 것이든 사용할 수 있다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있다. 선택한 정보가 \(X_i- X_k=d\)라면 \(d\)의 차이가 최초로 누적된다. \(X_k\)이후 \(X_j\)에 도달할 때까지 동일한 방식으로 차이를 누적한다. 동일한 연결에 대해서도 계산의 결과는 여러가지일 수가 있음에 주의하라.



\(X_i\)에서 \(X_j\)로의 가능한 모든 연결에 따라 \(X_i\)와 \(X_j\)의 차이의 모든 가능한 경우를 계산했을 때 전부 동일한 값이 나온다면 위의 첫번째 경우에 해당한다. \(X_i\)와 \(X_j\)의 가능한 연결이 존재하지 않는 경우 위의 두번째 경우에 해당한다. \(X_i\)와 \(X_j\)의 가능한 연결들을 이용해 \(X_i\)와 \(X_j\)의 차이를 계산했을 때 그 결과가 여러가지라면 위의 세번째 경우에 해당한다.



아래 입출력 예의 경우를 보자 입력은 아래와 같다. 

1

5 9

1 2 3 2

1 3 2 -2

2 2 3

1 3 2 -3

2 2 3

1 1 4 7

1 4 5 8

2 5 2

2 5 1



첫 줄의 “1”은 테스트 케이스의 개수이다. 테스트케이스의 첫번째 줄의 “5 9”는 변수가 5개 있으며 명령이 9개 있다는 뜻이다. 다음 줄의 “1 2 3 2”는 첫번째 종류의 명령이며 \(X_2-X_3=2\)라는 정보를 준다. 그 다음 줄은 \(X_3-X_2=-2\)라는 정보를 준다. 두 정보는 동일한 것임을 알 수 있다. 다음 줄의 “2 2 3”은 \(X_2-X_3\)에 대한 명령이다. \(X_2\)에서 \(X_3\)로의 연결의 예는 \([X_2, X_3], [X_2, X_3, X_2, X_3]\) 등이 있다. 모든 연결에서 계산한 값이 2로 동일함을 알 수 있다. 따라서 이 명령에 대한 답은 2이다. 다음 줄은 \(X_3-X_2=-3\)이라는 정보를 준다. 다음 명령은 “2 2 3”이다. \(X_2\)에서 \(X_3\)로의 가능한 연결인 \([X_2, X_3]\)에 대해 \(X_2-X_3=2\)라는 정보를 사용한 계산과 \(X_3-X_2=-3\)(동등하게 \(X_2-X_3=3)\)이라는 정보를 사용한 계산의 결과가 서로 다르므로 이 명령에 대한 답은 CF이다. 다음 명령인 “2 5 2”의 경우 \(X_5\)에서 \(X_2\)로의 가능한 연결이 없으므로 답은 NC이다. 마지막 명령의 답은 -15이다.



위와 같이 정해진 명령들을 처리하는 프로그램을 작성하시오. 

• 제한시간: 전체 테스트 케이스는 35개 이하이며, 전체 수행 시간은 5초 이내. (Java 8초 이내) 
  
      제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
  
      그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
  
      그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
  
      이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
  
      C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
  
      제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
  
      만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
  
• 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
  
• 제출 제한 : 최대 10회 (참고: 동점자의 경우 최고 점수에 도달한 시간에 제출 횟수 한번마다 7분의 지연을 부가하여 시간을 계산하고 이 시간이 빠른 순서대로 등수를 결정함)

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,

이후 차례로  \(T\) 개의 테스트 케이스가 주어진다. \((1 ≤ T ≤ 35) \)

각 테스트 케이스의 첫 줄에는 변수의 개수 \(N\)과 명령의 개수 \(K\)가 주어진다. \((1≤N≤100,000, 1≤K≤200,000) \)

둘째 줄부터 \(K\)개의 각 줄에는 명령이 하나씩 주어진다. 명령의 첫 수가 1인 경우 차이를 알려주는 것이다. “1 i j d”와 같이 주어진 경우 \(X_i-X_j=d\)라는 의미이다. 동일한 쌍의 변수에 대해 여러 개의 1번 종류 명령이 주어질 수 있다. 명령의 첫 수가 2인 경우 차이를 묻는 것이다. 즉, “2 i j”와 같이 주어진 경우 \(X_i-X_j\)를 묻는 것이다. 두 종류 모두 i와 j가 같을 수도 있다. d의 절대값은 10,000 이하이다.

• 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 200 점)
  
     주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
  
     각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
  
  
  
  ㆍ 그룹 1 (31 점) : 이 그룹의 테스트 케이스에서는 \(1≤N≤1,000, 1≤K≤2,000\)이다. 모든 1번 종류 쿼리에서 차이 값은 0이다.
  
  ㆍ 그룹 2 (28 점) : 이 그룹의 테스트 케이스에서는 \(1≤N≤1,000, 1≤K≤2,000\)이다.
  
  ㆍ 그룹 3 (20 점) : 이 그룹의 테스트 케이스에서는 모든 1번 종류 쿼리에서 차이 값은 0이다.
  
  ㆍ 그룹 4 (121 점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
  
  
  

• 모든 테스트 케이스를 풀지 않고 일부분의 그룹에 속하는 테스트 케이스만을 푸는 경우에도 입력 받은 모든 케이스에 대해 (답이 틀릴지라도) 출력 양식에는 맞는 출력을 생성해야 점수가 반영되는 것이 보장된다.

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #\(C\)”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.

그 다음 줄부터 각 쿼리에 대한 답을 한 줄에 출력한다.

입출력예

입력
1 5 9 1 2 3 2 1 3 2 -2 2 2 3 1 3 2 -3 2 2 3 1 1 4 7 1 4 5 8 2 5 2 2 5 1

출력
Case #1 2 CF NC -15

돌아가기