R00410
추 무게 비교
플래티넘 III레이팅
의견: 0
설명
\(1\)번부터 \(N\)번까지의 추가 있다. 처음에는 어떤 추의 무게 관계도 알지 못한다. 다음 두 종류의 명령을 순서대로 처리하여라.
! a b w: 추 \(b\)가 추 \(a\)보다 정확히 \(w\)만큼 무겁다는 사실이 알려진다. (\(w\)는 음수일 수도 있다)? a b: 지금까지 알려진 사실로부터 추 \(b\)가 추 \(a\)보다 얼마나 무거운지 유도할 수 있으면 그 값을, 유도할 수 없으면UNKNOWN을 출력한다.
주어지는 사실은 서로 모순되지 않는다. 명령이 섞여 들어오므로 자료 구조가 온라인으로 동작해야 한다. 두 추 사이의 상대 무게를 함께 관리하는 유니온 파인드가 필요하다.
제약
\(1 \le N \le 100{,}000\), \(1 \le Q \le 200{,}000\)
\(|w| \le 10^6\)이며, 주어지는 사실들은 항상 서로 모순되지 않는다.
입력 형식
첫 줄에 추의 수 \(N\)과 명령의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 명령이 위 형식으로 하나씩 주어진다.
출력 형식
각 ? 명령의 답을 입력 순서대로 한 줄에 하나씩 출력한다.
예제 1
입력
4 6
! 1 2 5
? 1 2
? 1 3
! 3 4 -2
! 2 3 1
? 1 4
출력
5
UNKNOWN
4설명
추 2는 추 1보다 5 무겁다. 추 3과의 관계는 아직 알 수 없다. 이후 \(w(3) = w(2) + 1 = w(1) + 6\), \(w(4) = w(3) - 2 = w(1) + 4\)를 유도할 수 있다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
추 무게 비교
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
추 무게 비교
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기