TLEoj Contest #09 - Mua bánh trung thu

Điểm: 3000 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Dạng bài

Trong lúc các bạn đang ngồi đánh vật với đề thi củ chuối (có $1$ bài troll) (và $3$ bài bait) này thay vì ra ngoài đi chơi Trung Thu như bao người khác (vì bạn vẫn đang bitchless) (hoặc đã trở thành social outcast) (hoặc gia đình bạn đã bỏ mặc bạn ở nhà và chở thằng/con em của bạn đi chơi), ở đâu đó trong thành phố Hà Nội, thằng ra đề đang đi ăn cùng với mấy đứa bạn của nó (chắc chắn không phải vì somehow sinh nhật thứ 16 của nó lại đúng vào đêm Trung Thu). Để giúp các bạn cảm thấy cuộc sống đỡ bất công hơn, thằng ra đề xin được phép kể một câu chuyện như sau.

Để chuẩn bị cho sinh nhật lần thứ 16 của mình (đồng thời cũng trùng vào đêm Trung Thu của năm $2123$ ), Lib đã nghĩ ra một ý tưởng vô cùng táo bạo (và khá hợp lí): Mua bánh trung thu thay cho bánh sinh nhật. Lib đã xác định được vị trí của N cửa hàng bán bánh trung thu trên thành phố. Vì muốn lần sinh nhật này trở thành troconbo lớn nhất từ trước đến nay, Lib muốn mua được nhiều bánh trung thu nhất có thể. Bình thường, mỗi lần ra đường, Lib chỉ toàn mặc đồng phục trường (không phải là do muốn ngạo nghễ trường chuyên vi en mà là do gu thời trang quá tệ và không biết mặc gì khác). Tuy nhiên, do đã gần đến Trung Thu và nhu cầu tiêu thụ bánh của mọi người đều rất cao, các cửa hàng chỉ bán bánh cho mỗi khách hàng đúng $1$ lần. Tất cả các chủ cửa hàng đều có khả năng nhớ mặt rất tốt - Lib đã thử cách chờ $10^9+7s$ rồi sau đó đến mua lại, và kết quả là bị chửi cho sấp mặt. Chợt nhớ đến việc ở nhà ông bà ngoại mới có $1$ bộ outfit cosplay gái alime mới mua (chắc chắn không phải do bị $1$ thằng nhóc lớp $9$ lên $10$ nào đó dụ mua để [REDACTED][REDACTED][REDACTED][REDACTED]), Lib đã vứt hết liêm sỉ đi để dùng bộ đồ cosplay làm disguise để đi mua bánh ở một cửa hàng nào đó (không nằm trong $N$ cửa hàng đã biết đến). Mọi chuyện đã rất suôn sẻ cho đến khi bác bán hàng - vi một lí do thần kì nào đó, check lại địa chỉ nhà và nhận ra Lib đã đến mua bánh trước đó $2 \times 10^9+7s$ rồi. Và thế là lại bị chửi sấp mặt. Bằng một cách thần kì nào đó, mọi chủ cửa hàng ở năm $2123$ đều là bậc thầy doxxing và biết được chính xác địa điểm mà Lib bắt đầu đạp xe ra khỏi nhà.

Bản đồ giao thông của thành phố Hà Nội (mà Lib cần quan tâm đến trong hành trình mua bánh này) gồm $N$ điểm - $N$ cửa hàng bánh trung thu và $N-1$ con đường hai chiều được đánh số từ $1$ tới $N-1$ . Con đường thứ $i$ trong số $N-1$ con đường này nối giữa $2$ điểm $U_i$ và $V_i$ với nhau, và Lib mất $T_i$ phút để đi hết con đường đó bằng xe đạp. Nhà của Lib nằm ở điểm $A$ , nhà ông bà nằm ở điểm $B$ (Đảm bảo $A$ $<$ $B$ , ở $2$ điểm $A$ và $B$ này cũng có cửa hàng bán bánh (nhưng mà là ở đối diện nhà)).

Ở thời điểm năm $2123$ , công nghệ dịch chuyển tức thời đã trở nên hoàn thiện - người người nhà nhà (bọn nhà giàu) ai ai cũng có các bộ dịch chuyển. Ở mỗi cửa hàng bán bánh đều có $1$ bộ dịch chuyển loại "xịn" - có thể dịch chuyển người dùng đến bất kì đâu trên hệ thống thành phố. Liên minh chủ của các tiệm bánh, tuy vô cùng ki bo, luôn sẵn sàng hỗ trợ k hháchàng di chuyển nhanh hơn (dĩ nhiên là sau khi họ đã mua bánh, chả ai ki bo đến mức tổng sỉ vả $1$ thằng bé vì nó muốn mua thêm bánh mà lại cho người ta teleport free cả). Dĩ nhiên, sự hỗ trợ này cũng chỉ là có giới hạn: Nếu chủ cửa hàng biết rằng khách hàng bắt đầu hành trình từ điểm $I$ và khoảng cách giữa điểm $I$ đó và tiệm bánh là $K$ , chủ cửa hàng sẵn sàng giúp khách hàng dịch chuyển và tiết kiệm $1$ khoảng cách tối đa là $K$ .
Cụ thể hơn, trong hình dưới đây, nếu khách hàng bắt đầu tại điểm $X$ và tiệm bánh ở điểm $Y$ , giả sử rằng độ dài cạnh của tất cả các ô vuông là như nhau, chủ tiệm sẽ vui vẻ giúp khách dịch chuyển nếu điểm đến mà khách hàng chọn thuộc vùng màu đỏ (còn nếu vào vùng màu đen là lại ăn chửi tiếp). Giả sử việc mua bánh dịch chuyển và thay quần áo là không mất thời gian, chỉ tính thời gian Lib phải di chuyển từ nhà đến các tiệm bánh bằng xe đạp.

(Giải thích ví dụ: Khoảng cách giữa $X$ và $Y$ trong hình đính kèm là $7$ . Vùng màu đỏ là những vùng $1$ khách hàng xuất phát từ $X$ , mua bánh ở $Y$ được phép dịch chuyển đến. Vùng màu xanh là vùng sẽ bị từ chối sử dụng thiết bị dịch chuyển + ăn chửi).

Nhà của Lib thì không giàu đến thế và chỉ có $1$ cặp bộ dịch chuyển loại "dởm": Khi cần, chỉ có thể dịch chuyển từ đầu này sang đầu kia của bộ dịch chuyển này. Gọi $2$ đầu này lần lượt là $I$ và $II$ . Tuy nhiên, do khả năng doxxing của các chủ tiệm bánh đã đạt đến một cảnh giới vô cùng vi diệu, các bác luôn biết được địa điểm bắt đầu của một hành trình mua bánh - kể cả khi sử dụng cổng dịch chuyển - vì vậy, nếu muốn việc mua bánh lần $2$ từ cùng $1$ cửa hàng trót lọt, $2$ hành trình đi mua bánh phải được bắt đầu ở $2$ địa điểm khác nhau . Ngoài ra, do xe đạp của Lib có khả năng chống xóc cực tệ (đến mức, nếu nó có ý thức, nó sẽ ngay lập tức trở thành "bartender of the year" ở mọi nơi mà nó đến) nên sau khi mua được $1$ cái bánh, Lib không thể mua thêm cái bánh nào khác mà phải trở về hoặc nhà (ở $A$ ) hoặc nhà ông bà (ở $B$ ) để cất bánh trước khi có thể mua thêm bánh mới. Ngoài ra, sau khi mua bánh xong, Lib cũng cần phải cất lại quần áo cosplay gái alime ở nhà ông bà (để không bị dính gay seggs allegations) và đảm bảo rằng $2$ đầu $I$ và $II$ được đặt về đúng chỗ của nó (để không bị ăn chửi vì làm mất đồ của gia đình).

Tính từ thời điểm lên ý tưởng, sau $18$ ngày và $45$ lần suy đi tính lại, Lib đã nghĩ được $1$ hành trình để có thể mua được nhiều bánh nhất có thể. Kể từ thời điểm đó đến sinh nhật Lib chỉ còn đúng $K$ phút để có thể đi mua bánh. Dù đã tính được số bánh tối đa có thể mua (và đã mất hết liêm sỉ đến mức sẵn sàng tống việc cosplay gái alime vào đề bài) và lên được hành trình tối ưu để mua bánh, Lib muốn thách thức bạn tìm ra được số bánh tối ưu và $1$ trong số các hành trình tối ưu thỏa mãn đó (để không bị @ trong lúc đang ăn sinh nhật). Nếu có nhiều hành trình mua được số bánh tối đa trong thời gian cho phép, in ra $1$ hành trình thỏa mãn bất kì. Bạn không cần phải in cụ thể chỉ dẫn cho tất cả các hành động - Lib sẽ tự động tìm cách để đi mua bánh với thời gian tối ưu theo phương pháp mà bạn tìm được. Nếu bạn tìm được $1$ hành trình mua được số bánh tối đa thỏa mãn (và in được ra), bạn sẽ được $100\%$ số điểm cho testcase đó. Nếu bạn chỉ xác định được số bánh trung thu tối đa có thể mua, bạn sẽ được $50\%$ số điểm cho testcase đó.

Yêu cầu: Tính số lượng bánh trung thu tối đa mà Lib có thể mua được, đồng thời in ra một thứ tự đi thăm các tiệm bánh thỏa mãn.

Input, Output, Contraints and Subtasks

Input

Dòng đầu tiên gồm $4$ số $N, A, B, K$ - lần lượt là số tiệm bánh, vị trí nhà chính và nhà ông bà ngoại của Lib, và thời gian còn lại (tính theo phút) cho đến sinh nhật Lib.
$N-1$ dòng tiếp theo, dòng thứ $i$ gồm $3$ số $U_i, V_i, T_i$ , trong đó:
$U_i, V_i$ : Điểm bắt đầu và kết thúc của đoạn đường thứ $i$ .
$T_i$ : Thời gian (tính theo phút) mà Lib cần để di chuyển giữa $2$ đầu của con đường thứ $i$ .

Output

Dòng thứ nhất gồm $1$ số $C$ - Số bánh trung thu lớn nhất mà Lib có thể mua được trong không quá $K$ phút.
Dòng thứ $2$ gồm $C$ số, số thứ $i$ tương ứng với nơi chiếc bánh thứ $i$ được mua.

Contraints

$2 \le N \le 300000$ .
$1 \le A, B \le N$ . Dữ liệu đầu vào đảm bảo $A$ khác $B$ .
$0 \le K \le 10^{18}$ .
$1 \le U_i, V_i \le N$ (với mọi $1 \le i \le N-1$ )
$1 \le T_i \le 10^6$ (với mọi $1 \le i \le N-1$ )
Mạng lưới đường đi liên thông: Có thể di chuyển giữa $2$ điểm bất kì trong số $N$ điểm cho sẵn chỉ bằng các con đường đã cho sẵn

Subtasks

Với các subtask từ $5$ đến $8$ , có $40\%$ số testcase thỏa mãn: Trên đường đi từ $A$ đến $B$ , mỗi tiệm bánh chỉ có đường đi trực tiếp đến tối đa $2$ tiệm bánh khác.
Subtask $1$ ( $7\%$ số điểm) : $N \le 300000$ , mỗi tiệm bánh chỉ có đường đi trực tiếp đến tối đa $2$ tiệm bánh khác, $A$ và $B$ chỉ kề với đúng 1 tiệm bánh, $K$ sẽ bằng thời gian di chuyển từ $A$ đến $B$ .
Subtask $2$ ( $8\%$ số điểm) : $N \le 35$ , mỗi tiệm bánh chỉ có đường đi trực tiếp đến tối đa $2$ tiệm bánh khác.
Subtask $3$ ( $9\%$ số điểm) : $N \le 350$ , mỗi tiệm bánh chỉ có đường đi trực tiếp đến tối đa $2$ tiệm bánh khác
Subtask $4$ ( $16\%$ số điểm): $N \le 300000$ , mỗi tiệm bánh chỉ có đường đi trực tiếp đến tối đa $2$ tiệm bánh khác
Subtask $5$ ( $10\%$ số điểm): $N \le 20$ .
Subtask $6$ ( $10\%$ số điểm): $N \le 100$ .
Subtask $7$ ( $10\%$ số điểm): $N \le 2000$ .
Subtask $8$ ( $30\%$ số điểm): Không có điều kiện gì thêm.

Example 1

Input

Output

7
2 7 5 3 2 4 1

Giải thích

Trong test ví dụ này, nhà của Lib ở $A$ , nhà ông bà ngoại ở $C$ .
Đầu I của bộ dịch chuyển đang ở $A$ , đầu $II$ của bộ dịch chuyển đang ở $C$
Lib sẽ lần lượt hành động như sau:

Xuất phát ở $A$ (mặc đồng phục), đi xe đạp đến $B$ mua bánh, cầm theo đầu $I$ (mất 2 phút). Khi đến $B$ , đặt đầu $I$ ở $B$ . Đã mua được bánh đầu tiên ở $B$ .
Từ $B$ , dịch chuyển đến điểm $M$ trên $BC$ mà có $BM=2$ (mất $0$ phút).
Từ $M$ , đi xe đạp đến $C$ , cất bánh (mất $2$ phút).
Đi xe đạp từ $C$ đến $G$ để mua bánh (mất $2$ phút). Đã mua được bánh thứ $2$ ở $G$ .
Dịch chuyển từ $G$ về $C$ (mất $0$ phút), cất bánh.
Cởi đồng phục, mặc cosplay ở $C$ (mất $0$ phút).
Đạp xe đến $E$ mua bánh (mất $5$ phút). Đã mua được bánh thứ 3 ở $E$ .
Dịch chuyển từ $E$ về $C$ (mất $0$ phút), cất bánh.
Chạy sang bên đường, mua bánh ở $C$ , về $C$ cất bánh (mất $0$ phút). Đã mua được bánh thứ 4 ở $C$ .
Dùng đầu $II$ (đang đặt ở $C$ ) ,dịch chuyển đến đầu $I$ đang đặt ở $B$ (mất $0$ phút). Lấy lại đầu $I$ . Mua bánh ở $B$ lần thứ $2$ . Đã mua được bánh thứ 5 ở $B$ .
Từ $B$ , dịch chuyển về $A$ , cất bánh (mất $0$ phút).
Đạp xe từ $A$ đến $D$ , mua bánh (mất $2$ phút). Đã mua được bánh thứ 6 ở $D$ .
Dịch chuyển từ $D$ về $A$ , cất bánh (mất $2$ phút).
Chạy sang bên đường ở $A$ , mua bánh, về $A$ cất bánh (mất $0$ phút). Đã mua được bánh thứ $7$ ở A. Đặt đầu $I$ trở lại $A$ .
Dùng đầu $I$ (đang ở $A$ ) dịch chuyển đến đầu $II$ (đang ở $C$ ). Cởi cosplay gái alime, mặc đồng phục (mất $0$ phút).
Dịch chuyển từ $C$ về $A$ , kết thúc hành trình (mất $0$ phút).
Tổng thời gian: $2+2+2+5+2+2 = 15$ phút.

Example 2

Input

Output

5
2 6 4 5 1

Giải thích

Trong test ví dụ này, nhà của Lib ở $A$ , nhà ông bà ở $E$ .
Đầu $I$ đang đặt ở $A$ , đầu $II$ đang đặt ở $E$ .
1 hành trình thỏa mãn:

Đi xe đạp từ $A$ đến $B$ , mua bánh ( $2$ phút). Mua bánh thứ nhất ở $B$
Dịch chuyển từ $B$ về $A$ , cất bánh ( $0$ phút)
Dịch chuyển từ đầu $I$ (đang ở $A$ ) đến đầu $II$ (đang ở $E$ ) ( $0$ phút).
Đi xe đạp từ $E$ đến $F$ , mua bánh ( $3$ phút). Mua bánh thứ 2 ở $F$
Dịch chuyển từ $F$ về $E$ , cất bánh ( $0$ phút)
Dịch chuyển từ đầu $II$ (đang ở $E$ ) đến đầu $I$ (đang ở $A$ ) ( $0$ phút)
Đi xe đạp từ $A$ đến $D$ , mua bánh ( $3$ phút). Mua bánh thư 3 ở $D$
Dịch chuyển từ $D$ về $A$ , cất bánh ( $0$ phút)
Dịch chuyển từ đầu $I$ (đang ở $A$ ) đến đầu $II$ (đang ở $E$ ) ( $0$ phút)
Chạy sang bên đường ở $E$ , mua bánh ( $0$ phút). Mua bánh thứ 4 ở $E$ . Chạy về nhà cất bánh
Dịch chuyển từ đầu $II$ (đang ở $E$ ) đến đầu $I$ (đang ở $A$ ) ( $0$ phút)
Chạy sang bên đường ở $A$ , mua bánh, chạy về nhà cất bánh ( $0$ phút). Bánh thứ 5 mua ở $A$ .
Tổng số bánh mua được: $5$
Tổng thời gian: $2+3+3=8$ (phút)

Example 3

Input

Output

8
4 2 3 6 5 3 1 7

Giải thích

Trong test ví dụ này, nhà của Lib ở $A$ , nhà ông bà ở $E$ .
Cổng $I$ đang ở $A$ , cổng $II$ đang ở $E$ .
Một lộ trình thỏa mãn:

Dịch chuyển từ cổng $I$ (đang ở $A$ ) đến cổng $II$ (đang ở $E$ ) ( $0$ phút)
Cởi đồng phục, mặc cosplay gái alime ở $E$ ( $0$ phút).
Đạp xe từ $E$ đến $D$ , mua bánh ( $2$ phút). Bánh $1$ được mua ở $D$ .
Dịch chuyển từ $D$ về $E$ , cất bánh ( $0$ phút).
Dịch chuyển từ cổng $II$ (đang ở $E$ ) đến cổng $I$ (đang ở $A$ ) ( $0$ phút)
Đạp xe từ $A$ đến $B$ , mua bánh ( $1$ phút). Bánh 2 được mua ở $B$
Dịch chuyển từ $B$ về $A$ , cất bánh ( $0$ phút)
Đạp xe từ $A$ đến $C$ , cầm theo cổng $I$ , mua bánh ( $3$ phút). Bánh 3 được mua ở $C$ . Đặt cổng $I$ tại $C$
Dịch chuyển từ $C$ đến $E$ , cất bánh ( $0$ phút).
Cởi quần áo cosplay, mặc đồng phục ở $E$ ( $0$ phút).
Đạp xe từ $E$ đến $F$ , mua bánh ( $3$ phút). Bánh 4 được mua ở $F$ .
Dịch chuyển từ $F$ về $E$ , cất bánh ( $0$ phút).
Chạy sang đường mua bánh ở $E$ , cất bánh ( $0$ phút). Bánh 5 được mua ở $E$ .
Dịch chuyển từ cổng $II$ (đang ở $E$ ) đến cổng $I$ (đang ở $C$ ). Lấy lại cổng $I$ . Mua bánh ( $0$ phút). Bánh 6 được mua ở $C$ .
Dịch chuyển từ $C$ về $A$ , cất bánh ( $0$ phút). Đặt cổng $I$ tại $A$ .
Chạy sang đường mua bánh ở $A$ , cất bánh ( $0$ phút). Bánh thứ 7 được mua ở $A$ .
Đạp xe từ $A$ đến $G$ , mua bánh ( $2$ phút). Bánh thứ 8 được mua ở $G$ .
Dịch chuyển từ $G$ về $A$ , cất bánh ( $0$ phút)
Tổng thời gian: $2+1+3+3+2=11$ (phút)
Số bánh mua được : $8$

Bình luận

Không có bình luận nào.