ACM-ICPC-OJ训练营

问题 G: Gear Up

时间限制: 8 Sec 内存限制: 128 MB
提交: 2 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:

1. They share a common edge (i.e. they have equal linear velocity).

2. They share a common shaft (i.e. they have equal angular velocity).

It is guaranteed that no pair of gears meets both of the above conditions.

A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.

Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.

sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

输入描述

There are multiple test cases (about

30).

For each test case:

The first line contains three integers

n,m,q, the number of gears, the number of adjacent pairs and the number of operations.

(0≤m<n≤105,0≤q≤105)

The second line contains

n integers, of which the

i-th integer represents

ri, the radius of the

i-th gear.

(ri∈{2λ∣0≤λ≤30})

Each of the next

m lines contains three integers

a,x,y, the

x-th gear and the

y-th gear are adjacent in the

a-th condition.

(a∈{1,2},1≤x,y≤n,x≠y)

Each of the next

q line contains three integers

a,x,y, an operation ruled in the following:

(a∈{1,2},1≤x≤n,y∈{2λ∣0≤λ≤30})

a=1 means to replace the

x-th gear with another one of radius

a=2 means to assign angular velocity

y to the

x-th gear and then determine the maximum angular velocity.

输出描述

For each test case, firstly output "Case #x:" in one line (without quotes), where

x indicates the case number starting from

1, and then for each operation of

a=2, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of

3 digits.

样例输入

样例输出

Case #1:
1.386
Case #2:
2.773
3.466
2.773