STARGATE - Stargates

Bài này bạn cần quản lý thông tin kết nối giữa các hành tinh.

Hành tinh A, B được kết nối nếu chúng có đường đi trực tiếp hoặc có 1 dãy các hành tinh

P1, P2,..Pn mà P1=A, Pn=B và có kết nối giữa Pk và Pk-1, k ∈ {2,..n}.

Kết nối là 2 chiều và có thể có nhiều kết nối giữa 2 thành phố.


Input

Gồm nhiều test, mỗi test vài dòng, mỗi dòng bắt đầu bằng ‘D’, ‘C’ hoặc ‘Q’ (chữ hoa hoặc

thường) sau đó là 1 -> 5 số nguyên với ý nghĩa như sau:

 

  • ‘D’ N -> xác định số hành tinh là N, N<=6000000, hành tinh đánh số từ 1..N.
  • ‘C’ -> tạo kết nối giữa các cặp hành tinh.
  • ‘Q’ -> kiểm tra các cặp hành tinh có kết nối.

Lệnh C và Q có cùng định dạng như sau (kí hiệu là chữ X )

X src dst – Tạo/truy vấn kết nối giữa 2 hành tinh src và dst

X src dst nnn – Tạo/truy vấn kết nối giữa hành tinh src và nnn hành tinh liên tiếp từ dst

VD: C 1 100 3 tạo 3 kết nối (1,100), (1,101), (1,102).

X src dst nnn step – Tạo/truy vấn kết nối giữa hành tinh src và nnn hành tinh bắt đầu từ

dst với bước nhảy là step.

VD: C 1 100 3 tạo 3 kết nối sau (1,100), (1,105), (1,110).

X src dst nnn dststep srcstep – Tạo/truy vấn kết nối giữa nnn cặp thành phố từ src với

bước nhảy là srcstep tại src và tới dst với bước nhảy là dststep.

VD: C 1 100 3 5 15 tạo 3 kết nối (1,100), (16,105), (31,110).

Output

Với mỗi truy vấn ‘Q’ in ra 2 số: số đầu tiên là số cặp thành phố kết nối,

số thứ hai là số cặp thành phố không kết nối trong truy vấn tương ứng.

Sample

 

Sample input: 
d 5
C 1 3
D 20
q 1 3
c 1 10 10
Q 1 2 18 1 1

Sample output:
0 1
9 9

Sample input 1:
d 5
d 1
q 1 1
d 10
q 1 6 5 1 1
c 1 2 9
q 1 6 5 1 1
Sample output 1:
1 0
0 5
5 0




 

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-27
Thời gian chạy:0.100s-0.925s
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:Southeastern European 2007

hide comments
2009-04-29 13:16:30 AnhDQ
??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.