시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 151 | 61 | 37 | 32.456% |
상트페테르부르크 시의 수로 길이의 총합은 약 282 km이고, 도시 면적 중 물이 차지하는 비중은 약 7%이다.
Wikipedia
상트페테르부르크는 n개의 섬을 m개의 다리로 이어 만든 도시이다. 섬은 1부터 n까지 정수로 표현할 수 있고, 다리는 1부터 m까지 정수로 표현한다. 각각의 다리는 서로 다른 두 섬을 연결한다. 어떤 다리는 표트르 대제 시절에 만들었고, 어떤 다리는 만든지 얼마 되지 않는다. 그래서 다리들마다 다양한 무게 제한이 있다. 즉, 자동차가 다리 i를 지나려면 무게가 di 이하여야 한다. 때떄로 상트페테르부르크의 다리들을 보수할 때가 있다. 그렇지만 보수를 한다고 꼭 다리가 더 튼튼해지는 것은 아니어서, di 값이 늘 수도 있고 줄어들 수도 있다. 이 도시의 시민과 관광객을 위해서, 다음 두 가지 질의를 처리할 수 있는 프로그램이 있다면 좋을 것이다.
두번째 형태의 질의를 모두 답하시오.
첫 번째 줄에는 두 정수 n, m가 주어진다. — 이는 각각 상트페테르부르크의 섬과 다리의 수이다. (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000)
다음 m 줄 중 i 번째 줄에는 세 정수 ui, vi, di가 주어지는데, 섬 ui과 섬 vi를 잇는 다리의 무게 제한은 최초에는 di라는 뜻이다. (1 ≤ ui, vi ≤ n; ui ≠ vi ; 1 ≤ di ≤ 109)
그 다음 줄에는 하나의 정수 q가 주어진다. — 이는 질의의 수이다. (1 ≤ q ≤ 100 000). 다음 q 줄에 질의가 주어진다.
각 질의는 정수 tj로 시작한다. (tj ∈ {1, 2})
만약 tj = 1이라면, 이 질의는 첫 번째 형태이고, 두 정수 bj와 rj가 뒤따라 주어지는데, 이는 다리 bj의 무게 제한이 rj로 바뀐다는 뜻이다. (1 ≤ bj ≤ m, 1 ≤ rj ≤ 109)
만약 tj = 2이면, 이 질의는 두번째 형태이고, 두 정수 sj와 wj가 뒤따라 주어지는데, 이는 무게가 wj인 자동차가 섬 sj에서 출발하여 도착할 수 있는 섬의 수를 구하라는 뜻이다. (1 ≤ sj ≤ n, 1 ≤ wj ≤ 109)
두번째 형태의 질의 하나마다 한 줄에 하나씩 질의의 답을 출력한다.
3 4 1 2 5 2 3 2 3 1 4 2 3 8 5 2 1 5 1 4 1 2 2 5 1 1 1 2 3 2
3 2 3
7 8 1 2 5 1 6 5 2 3 5 2 7 5 3 4 5 4 5 5 5 6 5 6 7 5 12 2 1 6 1 1 1 2 1 2 1 2 3 2 2 2 1 5 2 1 3 1 2 2 4 2 4 2 1 8 1 2 1 1 2 1 3
1 7 7 5 7 7 4
녹색 에지는 질의에서 물어보는 자동차가 건널 수 있는 다리를 나타낸다. 녹색 노드는 이 자동차가 도착할 수 있는 섬을 나타낸다. 화살표가 가리키는 섬은 이 자동차가 처음에 있던 곳이다.
첫 번째 테스트 데이터
두번째 테스트 데이터