Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Thu gom rác đánh dấu-và-quét (mark-and-sweep)

    Bộ thu gom rác đánh dấu-và-quét (mark-and-sweep) hoạt động trên một đồ thị đối tượng: có nnn đối tượng đánh số 1..n1..n1..n, đối tượng iii có kích thước szisz_iszi​ byte và có một danh sách con trỏ (cạnh có hướng) trỏ tới các đối tượng khác. Cho tập hợp rrr đối tượng gốc (root) — là các đối tượng được truy cập trực tiếp từ ngăn xếp hoặc biến toàn cục.

    Một đối tượng được coi là sống (live) nếu nó là gốc, hoặc có thể truy cập được từ một gốc bằng cách đi theo các con trỏ (không giới hạn số bước, đồ thị có thể có chu trình). Các đối tượng không sống bị giải phóng (sweep).

    Input:
4
10 20 5 7
2 2 3
1 4
0
1 1
1
1

Output:
FREED:
BYTES: 0

    (cả 4 đối tượng đều tới được từ gốc 1, kể cả qua chu trình 1→2→4→11 \to 2 \to 4 \to 11→2→4→1, nên không có gì bị giải phóng.)

    • Định dạng đầu vào:

      Dòng 1: số nguyên nnn (0≤n≤20000 \le n \le 20000≤n≤2000). Dòng 2: nnn số nguyên sz1,…,sznsz_1, \ldots, sz_nsz1​,…,szn​ — kích thước (byte) của đối tượng 1..n1..n1..n (bỏ qua dòng này nếu n=0n=0n=0). nnn dòng tiếp theo, dòng thứ iii mô tả cạnh ra của đối tượng iii: một số nguyên kik_iki​ rồi kik_iki​ số nguyên là id các đối tượng mà nó trỏ tới (kik_iki​ có thể bằng 0). Dòng cuối: số nguyên rrr rồi rrr số nguyên là id các đối tượng gốc.

    • Định dạng đầu ra:

      Dòng 1: FREED: theo sau là danh sách id các đối tượng bị giải phóng, sắp xếp tăng dần, cách nhau bởi dấu cách (nếu không đối tượng nào bị giải phóng thì chỉ in FREED:). Dòng 2: BYTES: T với TTT là tổng số byte của các đối tượng bị giải phóng.

    Ví dụ:

    Đầu vào:

    1
100
0
0

    Đầu ra:

    FREED: 1
BYTES: 100

    Đầu vào:

    4
10 20 5 7
2 2 3
1 4
0
1 1
1
1

    Đầu ra:

    FREED:
BYTES: 0

    Đang tải editor...