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
ngày thi 2 (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Ủ ĐỀ - ngày thi 2
#70295
royalsilver16 (Thành viên)
royalsilver16+1
Super fast coder
Bài viết: 78
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: ngày thi 2 8 năm trước   (+0)
chaos0000 viết:
QUOTE:
cho em hỏi bài 6 có trường hợp W>N ko ạ ? Em cảm ơn.

hình như trong đề có đảm bảo W < N
 
Đã lưu IP Đã lưu IP  
 
I do what I like
I like what I do
  Đã khóa chức năng gửi bài.
#70296
iamvozer (Thành viên)
iamvozer+1
Biết code binary-indexed tree
Bài viết: 30
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: ngày thi 2 8 năm trước   (+0)
Không biết bây giờ đã chấm chưa nhỉ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70298
phamvanlong54321 (Thành viên)
phamvanlong
Đã biết code đệ quy
Bài viết: 19
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: ngày thi 2 8 năm trước   (+0)
chấm được rồi đấy bạn !
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70299
warriorz (Thành viên)
warriorz
Đã biết code đệ quy
Bài viết: 16
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: ngày thi 2 8 năm trước   (+1)
Tình hình là test bài Tours có vẻ trâu nhỉ, chưa ai AC được
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70301
NovaDev (Thành viên)
novadev+7
Đã code là AC
Bài viết: 112
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: ngày thi 2 8 năm trước   (+0)
warriorz viết:
QUOTE:
Tình hình là test bài Tours có vẻ trâu nhỉ, chưa ai AC được =))


mình thề là đã làm đủ trò bệnh hoạn rồi mà vẫn ko thể lên được
 
Đã lưu IP Đã lưu IP  
 
... Nếu em là một bài NP, thì anh sẽ vét cạn để tìm ra lời giải ...
  Đã khóa chức năng gửi bài.
#70306
khuebeo (Admin)
beo_chay_so+62
Admin
Bài viết: 294
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: ngày thi 2 8 năm trước   (+1)
test bai TOURS13 dung la co hoi trau that, anh moi giam so T trong 1 so test va rejudge lai
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70307
NovaDev (Thành viên)
novadev+7
Đã code là AC
Bài viết: 112
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: ngày thi 2 8 năm trước   (+0)
khuebeo viết:
QUOTE:
test bai TOURS13 dung la co hoi trau that, anh moi giam so T trong 1 so test va rejudge lai


anh Khuê là psetter ạ

em vừa cài sol khác và AC rồi ạ hehe
 
Đã lưu IP Đã lưu IP  
 
... Nếu em là một bài NP, thì anh sẽ vét cạn để tìm ra lời giải ...
  Đã khóa chức năng gửi bài.
#70308
khuebeo (Admin)
beo_chay_so+62
Admin
Bài viết: 294
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: ngày thi 2 8 năm trước   (+0)
Em chia sẻ cách làm cho các bạn được không. Bài em chạy rất tốt.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70310
NovaDev (Thành viên)
novadev+7
Đã code là AC
Bài viết: 112
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: ngày thi 2 8 năm trước   (+0)
khuebeo viết:
QUOTE:
Em chia sẻ cách làm cho các bạn được không. Bài em chạy rất tốt.


Anh cho em hỏi chút được ko ạ ?, submit anh được 100/100 anh có dùng solution nào khác ngoài ijk từ n đỉnh ko ạ ?
 
Đã lưu IP Đã lưu IP  
 
... Nếu em là một bài NP, thì anh sẽ vét cạn để tìm ra lời giải ...
  Đã khóa chức năng gửi bài.
#70346
blazedragon (Thành viên)
Đã biết code đệ quy
Bài viết: 19
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: ngày thi 2 8 năm trước   (+0)
Các anh cho em hỏi bài COMNET của em sai ở đâu hay là TLE ạ.
Đây là code của em.
Code:
{$MODE OBJFPC}
program ComNet;
const
  InputFile  = '';//COMNET.INP';
  OutputFile = '';//COMNET.OUT';
  maxM = Round(1e6);
  maxN = Round(1e5);
type
  TEdge = record
    u, v : Integer;
    cost : Integer;
  end;
 
var
  e, tempE : array [1..maxM] of TEdge;
  n, m, Q : Integer;
  lab : array [1..maxN] of Integer;
  res : Int64;
  nTest, iTest : Integer;
  fi, fo : TextFile;
 
procedure Enter;
var
  i : Integer;
begin
  ReadLn(fi, n, m, Q);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, cost);
end;
 
procedure QSort(L, H : Integer);
var
  i, j : Integer;
  pivot, tmp : TEdge;
begin
  if L >= H then Exit;
  i := L; j := H;
  pivot := e[L + Random(H - L + 1)];
  repeat
    while e[i].cost < pivot.cost do Inc(i);
    while pivot.cost < e[j].cost do Dec(j);
    if i <= j then
      begin
        tmp := e[i]; e[i] := e[j]; e[j] := tmp;
        Inc(i); Dec(j);
      end;
  until i > j;
  QSort(L, j); QSort(i, H);
end;
 
function FindSet(const x : Integer) : Integer;
begin
  if lab[x] <= 0 then Exit(x);
  lab[x] := FindSet(lab[x]);
  Result := lab[x];
end;
 
procedure Union(const x, y : Integer);
begin
  if lab[x] < lab[y] then
    begin
      lab[y] := x;
      Exit;
    end;
  if lab[x] = lab[y] then dec(lab[y]);
  lab[x] := y;
end;
 
procedure Solve;
var
  tempX, tempY, tempC : Integer;
  i, j : Integer;
  k, s, t, c : Integer;
  x, y : Integer;
  count : Integer;
begin
  tempE := e;
 
  for j := 1 to Q do
    begin
      e := tempE;
 
      Read(fi, k, s);
      for i := 1 to s do
        begin
          Read(fi, t, c);
          e[t].cost := c;
        end;
      ReadLn(fi);
      tempX := e[k].u;
      tempY := e[k].v;
      tempC := e[k].cost;
 
      QSort(1, m);
 
      res := 0;
      FillChar(lab, SizeOf(lab), 0);
      count := 0;
 
      for i := 1 to m do
        begin
          x := FindSet(e[i].u);
          y := FindSet(e[i].v);
          if x <> y then
            begin
              res := res + e[i].cost;
              Union(x, y);
              Inc(count);
              if count = n - 1 then Break;
            end;
        end;
 
      res := res - tempC;
      FillChar(lab, SizeOf(lab), 0);
      Union(tempX, tempY);
      count := 1;
 
      for i := 1 to m do
        begin
          x := FindSet(e[i].u);
          y := FindSet(e[i].v);
          if x <> y then
            begin
              res := res - e[i].cost;
              Union(x, y);
              Inc(count);
              if count = n - 1 then Break;
            end;
        end;
 
      if res = 0 then
        WriteLn(fo, 'NO')
      else
        WriteLn(fo, 'YES');
    end;
end;
 
Begin
  Assign(fi, InputFile); Reset(fi);
  Assign(fo, OutputFile); Rewrite(fo);
  try
    ReadLn(fi, nTest);
    for iTest := 1 to nTest do
      begin
        Enter;
        Solve;
      end;
  finally
    Close(fi); Close(fo);
  end;
End.
Thuật toán của em là:
Code:
- Đầu tiên ta lưu lại tất cả các cạnh ban đầu.
- Với mỗi truy vấn ta phải gán lại mảng chứa các cạnh.
- Tìm trọng số của cây khung nhỏ nhất, lưu lại là resA.
- Tìm trọng số nhỏ nhất của cây khung có chứa cạnh k, lưu lại là resB.
- Nếu resA = resB thì kết quả là 'NO' nếu không thì là 'YES'.
 
Đã 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