Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - STNODE - Ai ACC được 100đ chỉ giáo giùm mình với!
#12879
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Bài này minh làm như sau:
B1. Tìm đường đi S,x1,x2,..xk,T
B2. Xét tất cả các xi, i=1,2,..,k
2.1. Loại bỏ đỉnh xi khỏi đồ thị
2.2. Tìm đường đi từ S --> T
Nếu không có đường đi thì xi là nút xung yếu.

Kết quả: 80đ.
Ai chỉ giúp em Test sai với!!!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12880
silly boy (Thành viên)
ronaldinho+3
Không code nữa rồi
Bài viết: 736
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Cách này ko phải sai mà là bị TLE bạn ạ
 
Đã lưu IP Đã lưu IP  
 
Vì tương lai con em chúng ta , kệ cha tương lai con em chúng nó
  Đã khóa chức năng gửi bài.
#12881
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Mình xem kết quả chạy chỉ có 0.6s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12882
khuc_tuan (Admin)
khuc_tuan+137
Admin
Bài viết: 1472
graph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Đó là thời gian chạy những test không bị TLE
Những test bị TLE thì sẽ bị ngắt giữa chừng nên không biết đc chạy mất bao lâu
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12883
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Vậy à, bây giờ thì em đã hiểu. Ai có thuật toán tốt chỉ giáo cho mình với!!!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12884
quynh6174 (Thành viên)
trangviet1304
Nhắm mắt code không bug
Bài viết: 123
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
cũng có thể cải tiến thuật toán của bạn 1 chút cho nó thành 100 như thế này :P
*bước 1 : với mỗi đỉnh là nút xung yếu trên đường đi từ s -->t.bạn gán luôn s bằng đỉnh đó để bước tìm đường tiếp theo có thể giảm đi tính toán --->ăn thêm 1 test là 90
*bước 2 : cố gắng xét + vứt bỏ những đỉnh chắc chắn ko là nút xung yếu trên đường đi bằng 1 vài trò bựa bựa khác :P
---> ăn thêm 1 test là 100 :P
 
Đã lưu IP Đã lưu IP  
 
  Đã khóa chức năng gửi bài.
#12885
cuongbn (Thành viên)
cuongbn
Đã biết code đệ quy
Bài viết: 7
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
vài trò bựa bựa thỉnh thoảng hữu ích ra phết ấy chứ nhỉ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12892
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Cảm ơn bạn Quỳnh!
+ Mình làm theo cải tiến 1 và đã đạt 90đ.
+ Vài trò bựa bựa của bạn là gì thì mình bó tay, chưa thể nào nghĩ ra!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#12894
ConanKudo (Admin)
conankudo+149
Admin
Bài viết: 782
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Bài này có thuật giải dùng DFS và BFS với độ phức tạp O(M+N),bạn có thể sang topic bàn luận để tham khảo hoặc hỏi cách DFS của anh Khúc Tuấn.
Cách của bạn mình nghĩ là bị TLE
 
Đã lưu IP Đã lưu IP  
 
There are times when you can't save others with just love and kindness.
  Đã khóa chức năng gửi bài.
#12895
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 11 năm, 10 tháng trước   (+0)
Mình xin phép post thuật toán tốt bên topic bàn luận ở đây nhé!!!
===========================================================================================
Bài 2: (của bạn Quang Vũ)
1. Tìm 1 đường đi bất kỳ từ s đến t, s=u0u1u2..uk=t
Gán nhãn cho các đỉnh này lần lượt là 0,1,2,..,k
Nhận xét: các đỉnh thỏa mãn phải thuộc đường đi này
2. Với mọi đỉnh u của đồ thị, tính f[u] với ý nghĩa
f[u] = đỉnh có nhãn lớn nhất đến được từ u mà không sử dụng các cạnh thuộc đường đi trên
3. Điều kiện để đỉnh ui thõa mãn là:
với mọi j < i, f[uj] <= i

Để tính f, có thể dùng dfs.
Độ phức tạp O(n+m).
===========================================================================================
Quá hay!!!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS