TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

52.2% (12/23)

Submission's AC Ratio

10.9% (20/183)

Tags

Description

還記得海鞘嗎?對,就是上次那隻視財如命的烏龜。
海鞘的藏寶窟群越蓋越大,到最後已經由原本的樹狀變成複雜的網狀結構。

他的藏寶窟群由V個藏寶窟組成、雙向連通的通道則有E條。
他希望安排一些守衛來巡邏每條道路。巡邏的龜則是這樣的:

每隻警衛會被安排一條巡邏路徑,每天早上三點會從路徑起點端巡邏到終點端、下午三點會從終點端回到起點。
海鞘希望每條通道都會恰好被巡邏到一次。

海鞘是數學一哥,他知道奇點有0個或2個時只需要一位警衛,超過2就不行了。
但是他也是節儉一哥,他希望僱用最少位警衛達成巡邏所有通道的任務。

海鞘找到了你,假設你幫他安排一組巡邏方案他就會給你109枚烏龜幣作為報酬。

==============================

本題不需進行輸入輸出,請先引入#include "lib1692.h"並使用以下函式完成任務:

*void Init(void);
在你作任何操作前請先呼叫這個函式。

*void GetVE(int&V, int&E);
只能呼叫一次,V表示藏寶窟的數量、E表示通道的數量。

*void Get(int&V1, int&V2);
能呼叫E次,第i次呼叫代表通道i是連接V1和V2。

*void ReportVst(int st);
*void ReportVed(int ed);
*void ReportE(int n);

用來回報一條路徑依序經過的通道編號。例如有一條1→2→4→2→5的巡邏路徑,
而通道1連接1和2、通道2連接4和2、通道3連接2和5、通道4連接2和4,
那麼你可以這樣回報:
ReportVst(1);  //代表巡邏起點為房間1
ReportE(1);    //代表走過通道1,走到房間2
ReportE(2);    //代表走過通道2,走到房間4
ReportE(4);    //代表走過通道4,走到房間2
ReportE(3);    //代表走過通道3,走到房間5
ReportVed(5);  //代表巡邏結束在房間5

*void Final(void);
表示已經輸出所有路徑,並會幫你結束程式。

==============================

Input Format

本題無須輸入,請依序使用Init()、GetVE()、E次Get()來讀取藏寶窟的資訊。

保證V ≤ 1,000,E ≤ 50,000

Output Format

本題無須輸出,請依照上述方法連續輸出所有人的巡邏路徑。

Hints

你可以在這裡載到一個測試用的.h檔。

例如對於以下藏寶窟結構:
5 4    //代表V=5,E=4,以下E行為編號1~4的通道兩端房間編號。
1 2
1 2
3 5
1 4

以下會是一個能通過此筆測試的程式碼:

#include <cstdio>
#include "lib1692.h"
int edge[50010][2], V, E;
int main() {
    Init();
    GetVE(V, E);
    for(int i=0; i<E; i++) Get(edge[i][0], edge[i][1]);
    ReportVst(1);
    ReportE(1);
    ReportE(2);
    ReportE(4);
    ReportVed(4);
    ReportVst(3);
    ReportE(3);
    ReportVed(5);
    Final();
}

(*)詳情見建國中學2010年校內模擬賽Contest 4 prob 1 / Contest 7 prob 2

Problem Source

原TIOJ1692 / ABCLS Contest, Problem B

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6