Ôn tuyển 2023 #2: Code mõm với IOI 23 - Ngày 1

Channel:

Lib

Subscribers:

120

Published on August 31, 2023 5:15:39 AM ● Video Link: https://www.youtube.com/watch?v=bpsbJffBHBg

Game:

Counter-Strike: Source (2004)

Duration: 3:00

48 views

0

đcm mạng mẽo như cặc
unironically fucking shit t ngồi nói 50p và nó archive lại 3p và stream disconnect mẹ nó luôn, hay đấy
oge, TLDR 50p nhé

B1: Cho 1 cây N đỉnh (n nhỏ hơn 2e5) n-1 cạnh, các cạnh được đánh trọng số, cần đánh trọng số các đỉnh sao cho tổng trọng số các đỉnh bé hơnk (k nhỏ hơn1e18). Có 2 đỉnh nguồn A,B
1 cặp đỉnh (i,j) được gọi là "thỏa mãn" nếu:
- ít nhất 1 trong 2 đỉnh i,j là đỉnh nguồn (hoặc cả 2)
- trên đường đi từ i đến j, nếu đi qua các điểm p1,p2,...,pt; độ dài đường đi từ i đến p[x] phải nhỏ hơn hoặc bằng p[x] với mọi x từ 1..t.
Yêu cầu: đếm số cặp đỉnh thỏa mãn lớn nhất trong mọi cách đánh trọng số các đỉnh.

Phần làm được:
Sub1 (8đ): khoảng cách giữa 2 đỉnh nguồn lớn hơn 2*k
(tương đương): mỗi đỉnh (nếu có) chỉ đến được từ 1 trong 2 đỉnh nguồn. DFS/BFS 2 lần để tìm khoảng cách từ 2 đỉnh nguồn đến mọi đỉnh, nhét vào vector, sort lại rồi tham.
fun story: ban đầu mình tưởng bài này cho trước trọng số đỉnh nên bảo bài này trivial. sau 2 tiếng mới phát hiện đọc sai đề. nhục như con chó, hehe
(để quote lời thằng Japenis nào đấy vàng 2 năm liên tiếp: nếu 1 bài khiến m phải code bỏng dái để cắn sub1 và có 6-7 sub, khả năng cao là bài khó. bài này mình literally ko nghĩ nổi thuật N^4 để cắn sub2 luôn, hehe)

B2: Interactive: Ở 1 vương quốc nào đó (cụ thể là Hungary 2023) có N địa điểm du lịch (N nhỏ hơn 256) được đánh số từ 0 đến n-1. Giữa 2 địa điểm có thể có tối đa 1 đường đi 2 chiều.
Ban đầu, không có thông tin về việc giữa 2 địa điểm (i,j) có đường đi hay không.
Gọi mật độ (density - d) của thành phố là x. Khi đó, mạng lưới đường đi thỏa mãn: giữa 3 địa điểm (i,j,k) bất kì, tồn tại ít nhất x cặp điểm được nối với nhau (dĩ nhiên x bé hơn 3)
Để kiếm thêm thông tin về hệ thống đường xá, được hỏi các câu hỏi có dạng:
- Input: 2 tập hợp A và B: (A[1],A[2],.....,A[x]), (B[1],B[2],.....,B[y]) là các thành phố đôi một khác nhau.
- Output: True nếu tồn tại 1 cặp (i,j) nào đó (i thuộc [1,x], j thuộc [1,y]) mà giữa A[x] và B[y] tồn tại đường nối trực tiếp, còn không thì là False
Yêu cầu: Sử dụng ít hơn 32640 câu hỏi, tìm ra đường đi dài nhất giữa 2 đỉnh trên đồ thị.

Nhận xét chung:
- Do 32640=256*255/2 nên dễ thấy ta có thể hỏi các câu hỏi có dạng (i,j) để trực tiếp tìm xem có cạnh nối giữa 2 đỉnh i và j không, từ đó dựng được đồ thị và làm như thường
- d=3: Đồ thị là đồ thị đầy đủ. Giữa 2 đỉnh bất kì đều có đường nối. cin n cout n
- d=2: Đồ thị không đầy đủ, nhưng liên thông. Quy về bài toán tìm đường đi dài nhất trên đồ thị liên thông (rất dễ vì n bé hơn 256 thì thuật N^3 vẫn ăn ngon, mà thuật chuẩn hình như cũng chỉ O(n) (bfs 2 lần))

Phần làm được:
Sub1: d=3 (5đ): Như trên
Sub2: d=2 (10đ): Như trên
Sub3+4 (45đ): d=1, được phép sử dụng không quá 32640 câu hỏi. Tương tự như sub2 nhưng với từng TPLT một, rồi sau đó tìm max.
......van khong tin bai nay chi co the va lam the cung duoc 60d

Other Statistics