trang chủ / đề bài / icpcwf16_f

Những con sông dài nhất

Đề bài

Mô tả

Hệ thống sông Chao Phraya là hệ thống sông chính của Thái Lan. Sáu con sông dài nhất của hệ thống, liệt kê theo độ dài giảm dần, là:

  • Tha Chin (765 km)
  • Nan (740 km)
  • Yom (700 km)
  • Ping (658 km)
  • Pa Sak (513 km)
  • Wang (335 km)

Hình dưới là mô hình đơn giản hóa của hệ thống sông này, trong đó các số trên cạnh là độ dài của từng đoạn sông. Điểm mà hai hay nhiều con sông gặp nhau khi chảy xuôi dòng gọi là một hợp lưu. Các hợp lưu được đánh số. Trong mô hình này, mỗi con sông hoặc kết thúc tại một hợp lưu, hoặc chảy ra biển; biển được đánh số là hợp lưu đặc biệt 0. Khi hai hay nhiều con sông gặp nhau tại một hợp lưu (khác hợp lưu 0), con sông hợp thành sau đó mang tên của một trong các con sông đó. Ví dụ, sông Ping và sông Wang gặp nhau tại hợp lưu 1, con sông hợp thành giữ tên Ping. Với cách đặt tên này, sông Ping dài 658 km còn sông Wang chỉ dài 335 km. Nếu con sông hợp thành được đặt tên là Wang thì sông Wang sẽ dài 688 km còn sông Ping chỉ dài 305 km.

dot
digraph {
  rankdir=LR;
  node [shape=circle];
  PaSak [shape=box, label="Pa Sak"];
  Nan [shape=box];
  Yom [shape=box];
  Wang [shape=box];
  Ping [shape=box];
  ThaChin [shape=box, label="Tha Chin"];
  Wang -> 1 [label="335", color=blue];
  Ping -> 1 [label="305", color=red];
  1 -> 0 [label="353", color=red];
  Yom -> 2 [label="700", color=orange];
  Nan -> 2 [label="675", color=purple];
  2 -> 0 [label="65", color=purple];
  PaSak -> 0 [label="513", color=green];
  ThaChin -> 0 [label="765"];
}

Hệ thống sông trong ví dụ thứ nhất. Các cạnh cùng màu thuộc cùng một con sông.

Việc mọi người ngày càng để ý tới hiện tượng này gây ra sự ganh đua gay gắt giữa các thị trấn ven sông. Chẳng hạn, người dân sống dọc sông Wang phản đối rằng biết đâu với một cách đặt tên hợp lý, con sông của họ thực ra có thể là dài nhất, hoặc dài thứ hai (hoặc ít nhất là không đứng cuối!). Để chấm dứt mọi phỏng đoán, nhiệm vụ của bạn là kiểm chứng tất cả những tuyên bố như vậy.

Thứ hạng của một con sông là vị trí của nó trong danh sách tất cả các con sông sắp theo độ dài giảm dần, thứ hạng tốt nhất là 1 dành cho con sông dài nhất. Với mỗi con sông, hãy xác định thứ hạng tốt nhất có thể của nó xét trên mọi cách đặt tên. Tại mỗi hợp lưu, trong mọi cách đặt tên, tên của con sông mới (lớn hơn) phải là một trong các tên của những con sông nhỏ hơn đổ vào hợp lưu đó. Nếu hai hay nhiều con sông có độ dài bằng nhau trong một cách đặt tên, tất cả các con sông bằng nhau đó đều được coi là có thứ hạng tốt nhất có thể. Ví dụ, nếu một con sông dài nhất và mọi con sông còn lại có độ dài bằng nhau thì các con sông còn lại đều có thứ hạng 2.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n (1≤n≤500000) là số nguồn sông trong hệ thống và m (0≤m≤n−1) là số hợp lưu có nhãn dương. Các hợp lưu này được đánh số từ 1 tới m.

n dòng tiếp theo mô tả các con sông. Mỗi dòng gồm một xâu là tên của con sông tại nguồn, và hai số nguyên c (0≤c≤m) và d (1≤d≤109), trong đó c là số hiệu của hợp lưu gần nhất ở hạ lưu và d là khoảng cách (tính bằng km) từ nguồn tới hợp lưu đó. Tên sông chỉ gồm các chữ cái thường và hoa từ a tới z, có độ dài từ 1 tới 10 ký tự.

m dòng cuối mô tả các hợp lưu 1 tới m theo cách tương tự. Dòng thứ k trong số này mô tả hợp lưu có số hiệu k và chứa hai số nguyên: số hiệu của hợp lưu gần nhất ở hạ lưu và khoảng cách (tính bằng km) từ hợp lưu k tới hợp lưu đó.

Dữ liệu bảo đảm mỗi hợp lưu từ 1 tới m xuất hiện ít nhất hai lần với vai trò "hợp lưu gần nhất ở hạ lưu", hợp lưu 0 xuất hiện ít nhất một lần, và mọi nguồn sông đều chảy tới hợp lưu 0.

Dữ liệu ra

In mỗi con sông trên một dòng, theo đúng thứ tự trong dữ liệu vào. Trên mỗi dòng in tên con sông và thứ hạng tốt nhất có thể của nó.

Ràng buộc

  • 1≤n≤500000, 0≤m≤n−1.
  • 0≤c≤m, 1≤d≤109 (với cả nguồn sông và hợp lưu).
  • Tên sông gồm từ 1 tới 10 chữ cái tiếng Anh thường hoặc hoa.

Ví dụ

Input Output Giải thích
6 2
PaSak 0 513
Nan 2 675
Yom 2 700
Wang 1 335
Ping 1 305
ThaChin 0 765
0 353
0 65
PaSak 5
Nan 2
Yom 1
Wang 3
Ping 4
ThaChin 1
Hệ thống sông trong hình. Nếu hợp lưu 1 mang tên Wang thì Wang dài 688 km; khi đó dù đặt tên thế nào, Tha Chin (765 km) và một trong hai sông Nan (740 km nếu hợp lưu 2 mang tên Nan) hoặc Yom (765 km nếu mang tên Yom) vẫn dài hơn, nên thứ hạng tốt nhất của Wang là 3.
3 1
Ab 1 5
Cd 1 5
Ef 0 9
0 4
Ab 1
Cd 1
Ef 1
Ab và Cd gặp nhau tại hợp lưu 1. Con sông được chọn đi tiếp dài 5+4=9 km, bằng sông Ef, con còn lại dài 5 km. Mỗi sông đều có thể đạt thứ hạng 1 vì các sông dài bằng nhau cùng nhận thứ hạng tốt nhất.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0