TopCoder

User's AC Ratio

94.7% (18/19)

Submission's AC Ratio

64.1% (25/39)

Description

有一天,喵喵想要去別的縣市玩,於是他選出了N個候選的縣市,從0編號到N-1。這些縣市都是由很多個鄉鎮構成,從0編號到M-1(M是該縣市的鄉鎮數量)。兩個不同的鄉鎮間可能會有一條雙向道路連接(總共K條道路,編號為0~K-1),但是任兩個鄉鎮間恰有唯一的路徑通行(可能經過別的鄉鎮)。每條道路的長度有可能不一樣,但是一定是正整數。
喵喵的時間不多,他只想要從其中挑出兩個縣市前往:「可以玩最久的」和「可以最快玩完的」。

可是要計算去每個縣市玩要花的確切時間太麻煩了,喵喵發現「縣市中要走最遠才能到的兩鄉鎮之間的距離P」(以下簡稱「鄉鎮最遠距離」,在Hints當中有一個例子)愈長,花費的時間就愈長,反之則反。因此,只要找到了「鄉鎮最遠距離」最長和最短的縣市,就找到了「可以玩最久的」和「可以最快玩完的」的縣市。
但是喵喵仍然覺得這樣要處理的東西太多。還好,他找到了一個具有法力的機器X,可以瞬間回答任兩個縣市哪一個的「鄉鎮最遠距離」比較長。

你的任務是幫喵喵操作機器X,並且告訴喵喵,可以玩最久的和可以最快玩完的縣市的「鄉鎮最遠距離」分別是多少,以方便他安排行程。
由於你的法力和計算能力都不強,你操作機器X的次數和取得縣市地圖的次數都沒辦法太多。保證任兩個縣市的「鄉鎮最遠距離」都不一樣。

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

請記得#include "lib1164.h"。以下是幾個你可以使用的函式:

int init();:你應該要在進行任何操作前呼叫這個函式。本函式會回傳喵喵候選的縣市數量N。
int query(int a, int b);:操作機器X的指令,代表詢問編號a和b的縣市哪一個「鄉鎮最遠距離」比較長。如果是a,回傳1,否則回傳0。如果呼叫次數超過限制,你會得到一個WA
MAP getct(int a);:這個函數會回傳一個特殊的型別MAP代表編號a的縣市的地圖。假設變數名稱為pp.m代表該縣市的鄉鎮數量;p.k代表該縣市的道路數量;p.xp.yp.len都是長度為k的陣列,代表這個縣市編號i的道路長度為p.len[i],並連接編號p.x[i]p.y[i]的鄉鎮。如果呼叫次數超過限制,你會得到一個WA
MAP型別的詳細資訊請參考Hints。)
void answer(int longest, int shortest);:計算完之後,呼叫這個函式提交答案,兩個參數依序為可以玩最久的和可以最快玩完的縣市的「鄉鎮最遠距離」。這個函式會幫你結束程式。

對於所有的測資,$2 \leq N,M,K \leq 10^ 6$。
保證答案一定在int範圍內。

子任務(測資) 額外限制 分數
1 (0~3) $N,M,K \leq 4 \times 10^3$ 20
2 (4~7) $N,M,K \leq 4 \times 10^3$,
最多只能呼叫getct 5次
10
3 (8~11) 最多只能呼叫getct 3次 11
4 (12~15) 最多只能呼叫getct 2次、呼叫query 30N次 12
5 (16~19) 最多只能呼叫getct 2次,且呼叫query的次數不超過最少足夠求解的次數 47

(註:對於第一組子任務來說,getct的次數無限制;而對於前三組子任務來說,query的次數無限制)

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Sample Input

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
2
7 6 7
0 2 3
1 2 1
2 3 3
4 1 1
5 2 4
6 1 2
5 4 12
1 0 1
2 1 5
3 1 3
4 1 7

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
12 7
12 7
correct

Hints

typedef struct { int m, k; int *x, *y, *len; } MAP;
以上是MAP型別的原型。

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:N;
接下來依序為編號0~N-1的縣市的資料,每個縣市的格式皆如下:
第一行:m, k, p;(分別是鄉鎮數量、道路數量和鄉鎮最遠距離)
接下來k行:x, y, len;(代表有一條長度為len的道路連接編號為x和y的鄉鎮)
此程式將會輸出三行:
第一行:你呼叫answer的兩個參數;
第二行:正確答案;
第三行:呼叫answer的參數是否與答案相同,相同輸出correct,否則輸出incorrect

下圖為範例測資的圖示。
方框代表縣市,旁邊的數字是編號;圓圈代表鄉鎮,裡面的數字是編號;鄉鎮之間的線代表道路,旁邊的數字代表長度。

縣市0中走最遠才能到的兩鄉鎮是鄉鎮3和鄉鎮5,因此鄉鎮最遠距離等於4+3=7。
同理,縣市1的鄉鎮最遠距離等於12。
由於只有兩個縣市,鄉鎮最遠距離最長的是縣市1、最短的是縣市0。

Problem Source

Judge / Description by Yihda Yol
建國中學105學年度校隊選拔:複試pC

Subtasks

For Testdata: 0 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 10
For Testdata: 8 ~ 11, Score: 11
For Testdata: 12 ~ 15, Score: 12
For Testdata: 16 ~ 19, Score: 47
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 131072 65536
1 2000 131072 65536
2 2000 131072 65536
3 2000 131072 65536
4 2000 131072 65536
5 2000 131072 65536
6 2000 131072 65536
7 2000 131072 65536
8 2000 131072 65536
9 2000 131072 65536
10 2000 131072 65536
11 2000 131072 65536
12 2000 131072 65536
13 2000 131072 65536
14 2000 131072 65536
15 2000 131072 65536
16 2000 131072 65536
17 2000 131072 65536
18 2000 131072 65536
19 2000 131072 65536