HWAYADS - Highway Advertising

Sau nhiều năm chuẩn bị kĩ càng về cơ sở vật chất, IOI2023 được chọn tổ chức tại Việt Nam, đây quả là một sự kiện lớn cho giới hâm mộ tin học nước nhà! Thi tài là một chuyện, không thể để các vị khách quý tới thăm Việt Nam mà không đi thăm N điểm du lịch (đánh số từ 0..N-1) vốn từ lâu đã nổi tiếng ở cả trong và ngoài nước. Tất nhiên, thủ đô Hà Nội của chúng ta (được đánh số 0) là nơi khởi hành của tour du lịch đặc biệt này! Sau nhiều năm xây dựng, hệ thống giao thông ở Việt Nam đã hiện đại tới mức chỉ cần đúng N-1 con đường cao tốc một chiều nối các điểm du lịch là các vị du khách đã có thể đi tới cả N điểm du lịch trên hành trình. Chưa hết, bộ Văn hóa Thể thao & Du lịch còn nảy ra ý tưởng sơn lên các con đường những câu khẩu hiệu nhằm quảng bá cho kì thi IOI lần này, cũng như giới thiệu tới các du khách về đất nước Việt Nam xinh đẹp. KTuấn vốn là vCoder máu mê mấy sự kiện này nên đã trở về Việt Nam từ sớm, trong mấy ngày ở Hà Nội, KTuấn tình cờ gặp AnhDQ (vốn là đệ tử ruột của mình ;)) ), lại được nghe thông tin về ý tưởng hay ho kia, KTuấn liền nảy ra ý định thử tài nhóc đệ tử bằng cách phán một câu khẩu hiệu và hỏi AnhDQ xem: nếu đi từ Hà Nội tới các điểm du lịch thì KTuấn có thể nhìn thấy câu khẩu hiệu đó bao nhiêu lần?. Lâu ngày gặp lại, AnhDQ (vốn hay ngứa chân đi khắp đất Việt) mà lúng túng trước câu hỏi đơn giản của KTuấn thì ngại lắm :"> Cho trước dữ liệu về các con đường, bạn hãy giúp AnhDQ giữ thể diện xem sao nhé!

Dữ liệu

- Dòng thứ nhất chứa số N.
- N-1 dòng sau, mỗi dòng chứa 2 số u, v và xâu kí tự S, thể hiện con đường cao tốc từ u tới v, trên đó có sơn xâu S theo chiều từ u->v.
- Dòng cuối cùng chứa câu khẩu hiệu mà KTuấn thách đố AnhDQ.

Kết quả

- Gồm một số duy nhất là câu trả lời của AnhDQ.

Ví dụ

Dữ liệu:
11
0 2 Welcom
0 7 VietN
2 8 nauTK
7 3 am
7 9 nauTK
2 5 eKTuan
5 4 IOIKTuanIO
7 1 IOI
5 6 IOI23
4 10 I2023
KTuanIOI

Kết quả:
3

*** Giải thích:
Trên đường 0-2-5-6: WelcomeKTuanIOI23
Trên đường 0-2-5-4-10: WelcomeKTuanIOIKTuanIOI2023

Giới hạn

- N ≤ 17032.
- Độ dài các xâu ≤ 1000.
- Độ dài câu khẩu hiệu của KTuấn ≤ 70.


Được gửi lên bởi:AnhDQ
Ngày:2009-05-06
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:AnhDQ (re-covered)

hide comments
2017-12-14 04:46:54


Last edit: 2020-08-31 17:58:21
2013-08-05 16:24:46 Chuyên Triết Tổng Hợp
hash =))

Last edit: 2013-08-05 16:25:01
2009-05-08 05:00:07 Nguyễn Mai Lan
Well, KMP on tree is enough :D
Don't need to use DP :)
2009-05-07 17:44:48 Race with time
By the way, spelling mistake:
"KTuan has a slogan in his mine" -> "his mind"
[AnhDQ]: thx, i corrected it

Last edit: 2009-05-08 04:33:50
2009-05-07 17:15:20 Race with time
Thanks! Replacing "<=" by "<" made it get 80 points.
I'm considering the way to improve the DP.
Anyway, I keep my opinion that 1s is quite strict for this problem.

Last edit: 2009-05-07 17:15:49
2009-05-07 15:42:39 AnhDQ
KMP works well, sure ;) your 2375755 submit has 2 TLE tests only, but WA some ^^
2009-05-07 09:19:38 Race with time
Time limit is somewhat strict. :)
I think 2-3s is reasonable :?

Last edit: 2009-05-07 09:20:43
2009-05-07 06:13:43 Race with time
KMP + DP on tree :?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.