TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

92.9% (26/28)

Submission's AC Ratio

44.3% (58/131)

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

No. Testdata Range Score
1 0~3 20
2 4~7 10
3 8~11 11
4 12~15 12
5 16~19 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 131072 262144 1
1 2000 131072 262144 1
2 2000 131072 262144 1
3 2000 131072 262144 1
4 2000 131072 262144 2
5 2000 131072 262144 2
6 2000 131072 262144 2
7 2000 131072 262144 2
8 2000 131072 262144 3
9 2000 131072 262144 3
10 2000 131072 262144 3
11 2000 131072 262144 3
12 2000 131072 262144 4
13 2000 131072 262144 4
14 2000 131072 262144 4
15 2000 131072 262144 4
16 2000 131072 262144 5
17 2000 131072 262144 5
18 2000 131072 262144 5
19 2000 131072 262144 5