29.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 กลุ่มติวหนังสือ

ระดับง่าย เวลาไม่เกิน 1 วินาที

ก่อนสอบปลายภาค นักเรียน N คน หมายเลข 1 ถึง N จับคู่ติวหนังสือกัน M ครั้งตามลำดับ ครั้งที่ i นักเรียน a_i กับ b_i นั่งติวด้วยกัน ครูนับว่านักเรียนสองคนอยู่ กลุ่มติวเดียวกัน ถ้าเคยติวด้วยกันโดยตรง หรือเชื่อมกันผ่านคนอื่น เช่น ถ้า 1 ติวกับ 2 และ 2 ติวกับ 5 ก็นับว่า 1 กับ 5 อยู่กลุ่มเดียวกัน

ครูให้ทุกคู่ที่อยู่กลุ่มเดียวกันแลกสรุปบทเรียนให้กัน หลังการติวแต่ละครั้ง ให้บอกว่าตอนนี้มีนักเรียนกี่คู่ที่อยู่กลุ่มติวเดียวกัน คู่ของ x กับ y นับเป็นคู่เดียว ไม่สนว่าใครมาก่อน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 200000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i และ b_i คั่นด้วยช่องว่าง โดยที่ 1 ≤ a_i, b_i ≤ N และ a_i ≠ b_i คู่เดิมอาจติวกันซ้ำได้หลายครั้ง

ข้อมูลออก

M บรรทัด บรรทัดที่ i คือจำนวนคู่ของนักเรียนที่อยู่กลุ่มติวเดียวกันหลังการติวครั้งที่ i

1
1
2

ดูคำใบ้

สองกลุ่มขนาด s_a กับ s_b รวมกัน คู่ใหม่ที่เกิดขึ้นคือคนหนึ่งจากกลุ่มแรกจับกับคนหนึ่งจากกลุ่มที่สอง มี s_a × s_b คู่ คู่เดิมในแต่ละกลุ่มยังอยู่ครบ จึงบวกเพิ่มแค่นี้ ถ้าสองคนอยู่กลุ่มเดียวกันอยู่แล้ว จำนวนคู่ไม่เปลี่ยน union-find ที่เก็บขนาดกลุ่มไว้ที่หัวหน้าบอก s_a กับ s_b ได้ทันที แต่ต้องอ่านก่อนรวม เพราะรวมแล้วขนาดที่หัวหน้าเปลี่ยน นักเรียนสองแสนคนอยู่กลุ่มเดียวกันมีราว 2 × 10¹⁰ คู่ เกิน int ถ้าทุกครั้งที่รวมไล่เปลี่ยนหมายเลขกลุ่มของทั้งห้อง จะเป็น O(NM) ไม่ทันเมื่อ N กับ M เป็นแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    long long pairs = 0;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int root_a = find_root(a);
        int root_b = find_root(b);
        if (root_a != root_b) {
            pairs += (long long)group_size[root_a] * group_size[root_b];
            if (group_size[root_a] < group_size[root_b]) {
                swap(root_a, root_b);
            }
            parent[root_b] = root_a;
            group_size[root_a] += group_size[root_b];
        }
        cout << pairs << '\n';
    }
    return 0;
}

ข้อ 2 ถนนเส้นแรกที่ทำให้วน

ระดับง่าย เวลาไม่เกิน 1 วินาที

จังหวัดหนึ่งมีอำเภอ N อำเภอ หมายเลข 1 ถึง N ตอนแรกไม่มีถนนเลย กรมทางหลวงสร้างถนน M เส้นตามลำดับ เส้นที่ i เชื่อมอำเภอ a_i กับ b_i วิ่งได้สองทาง

กรมทางหลวงอยากรู้ว่างบส่วนไหนใช้ไปกับถนนที่ไม่ได้ทำให้ไปที่ใหม่ได้ ถนนเส้นหนึ่ง ทำให้วน ถ้าตอนที่สร้างเสร็จ อำเภอ a_i กับ b_i ไปมาหากันได้อยู่แล้วผ่านถนนที่สร้างก่อนหน้า ให้หาว่าถนนเส้นแรกที่ทำให้วนคือเส้นที่เท่าไร และมีถนนที่ทำให้วนทั้งหมดกี่เส้น

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i และ b_i คั่นด้วยช่องว่าง โดยที่ 1 ≤ a_i, b_i ≤ N และ a_i ≠ b_i อาจมีถนนหลายเส้นเชื่อมคู่อำเภอเดียวกัน

ข้อมูลออก

บรรทัดแรกพิมพ์ลำดับของถนนเส้นแรกที่ทำให้วน นับเส้นแรกเป็นเส้นที่ 1 ถ้าไม่มีถนนเส้นไหนทำให้วนเลย ให้พิมพ์ 0 บรรทัดที่สองพิมพ์จำนวนถนนที่ทำให้วนทั้งหมด

5
2

0
0

ดูคำใบ้

ใส่ถนนตามลำดับลง union-find ถนนที่ unite รวมไม่ได้ เพราะสองเมืองอยู่กลุ่มเดียวกันแล้ว คือถนนที่ทำให้เกิดทางวนตามหน้า 29.2 จำเส้นแรกที่เจอไว้ แต่ยังต้องอ่านและนับต่อจนครบทุกเส้น ตรวจคำตอบบรรทัดที่สองด้วยสูตร M - (N - C) เมื่อ C คือจำนวนกลุ่มตอนจบ ถนนที่ซ้ำกับเส้นเดิมก็ทำให้วน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    int first = 0, loops = 0;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (!unite(a, b)) {
            loops++;
            if (first == 0) {
                first = i;
            }
        }
    }
    cout << first << '\n';
    cout << loops << '\n';
    return 0;
}

ข้อ 3 วางท่อประปาหมู่บ้าน

ระดับง่าย เวลาไม่เกิน 1 วินาที

อำเภอหนึ่งมีหมู่บ้าน N แห่ง หมายเลข 1 ถึง N การประปาสำรวจแนวที่วางท่อได้ M แนว แนวที่ i เชื่อมหมู่บ้าน a_i กับ b_i ราคา c_i บาท น้ำไหลในท่อได้ทั้งสองทาง การประปาอยากเลือกวางท่อบางแนว ให้น้ำจากหมู่บ้านใดก็ได้ไหลไปถึงทุกหมู่บ้าน โดยราคารวมน้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000 และ 0 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i b_i และ c_i คั่นด้วยช่องว่าง โดยที่ 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i และ 1 ≤ c_i ≤ 10⁹ หมู่บ้านคู่เดียวกันอาจมีหลายแนว

ข้อมูลออก

ราคารวมที่น้อยที่สุด ถ้าวางท่อทุกแนวแล้วก็ยังไม่ถึงทุกหมู่บ้าน ให้พิมพ์ -1

-1

ดูคำใบ้

ทำ Kruskal ตามหน้า 29.3 เก็บแนวท่อเป็น tuple ที่ราคาอยู่ช่องแรก เรียง แล้วหยิบแนวที่สองปลายอยู่คนละกลุ่มของ union-find ถ้าหยิบได้ไม่ครบ N - 1 แนว แปลว่าต่อไม่ครบ ให้พิมพ์ -1 ราคารวมถึงราว 10¹⁴ ต้องใช้ long long ถ้าตรวจว่าสองหมู่บ้านถึงกันแล้วหรือยังด้วย BFS ทุกแนว จะเป็น O(NM) ซึ่งไม่ทันเมื่อ N เป็นแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> pipes(m);
    for (int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        pipes[i] = {cost, a, b};
    }
    sort(pipes.begin(), pipes.end());
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    long long total = 0;
    int used = 0;
    for (auto [cost, a, b] : pipes) {
        if (unite(a, b)) {
            total += cost;
            used++;
        }
    }
    if (used == n - 1) {
        cout << total << '\n';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}

ข้อ 4 รวมห้องแชต

ระดับกลาง เวลาไม่เกิน 1 วินาที

แอปแชตของโรงเรียนมีผู้ใช้ N คน หมายเลข 1 ถึง N ตอนเริ่ม ผู้ใช้หมายเลข i อยู่คนเดียวในห้องแชตหมายเลข i ระบบรับคำสั่ง Q คำสั่งตามลำดับ มีสองแบบ

1 a b ย้ายทุกคนในห้องที่ b อยู่ เข้าไปในห้องที่ a อยู่ ห้องที่รวมแล้วใช้หมายเลขห้องของ a ต่อไป ส่วนหมายเลขห้องเดิมของ b เลิกใช้ ถ้า a กับ b อยู่ห้องเดียวกันอยู่แล้ว ไม่มีอะไรเปลี่ยน
2 a ถามว่าตอนนี้ a อยู่ห้องหมายเลขอะไร และห้องนั้นมีสมาชิกกี่คน นับ a ด้วย

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 400000

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน โดยที่ 1 ≤ a, b ≤ N และ a กับ b อาจเป็นคนเดียวกันได้

ข้อมูลออก

ตอบคำสั่งแบบ 2 ตามลำดับ คำสั่งละหนึ่งบรรทัด มีหมายเลขห้อง และจำนวนสมาชิกในห้อง คั่นด้วยช่องว่าง

ดูคำใบ้

ใครอยู่ห้องเดียวกับใครเป็นงานของ union-find ขนาดห้องอ่านได้จาก group_size ที่หัวหน้า แต่หมายเลขห้องไม่ใช่หมายเลขของหัวหน้าเสมอไป union by size อาจเลือกหัวหน้าจากฝั่งของ b เพราะห้องของ b ใหญ่กว่า ให้เก็บหมายเลขห้องไว้อีกอาเรย์หนึ่งที่ตำแหน่งหัวหน้า ก่อนรวมจำหมายเลขห้องของ a ไว้ รวมเสร็จแล้วค่อยเขียนลงที่หัวหน้าคนใหม่ ถ้ารวมห้องโดยไล่เปลี่ยนหมายเลขห้องของผู้ใช้ทุกคน จะเป็น O(NQ) ไม่ทันเมื่อรวมห้องเป็นแสนครั้ง และ find แบบ recursion ที่ไม่มี union by size อาจพังด้วย stack overflow

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size, room;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    room.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        room[i] = i;
    }
    for (int k = 0; k < q; k++) {
        int type, a;
        cin >> type >> a;
        if (type == 1) {
            int b;
            cin >> b;
            int root_a = find_root(a);
            int root_b = find_root(b);
            if (root_a == root_b) {
                continue;
            }
            int name = room[root_a];
            if (group_size[root_a] < group_size[root_b]) {
                swap(root_a, root_b);
            }
            parent[root_b] = root_a;
            group_size[root_a] += group_size[root_b];
            room[root_a] = name;
        } else {
            int root = find_root(a);
            cout << room[root] << ' ' << group_size[root] << '\n';
        }
    }
    return 0;
}

ข้อ 5 ถนนเก่ากับถนนใหม่

ระดับกลาง เวลาไม่เกิน 1 วินาที

จังหวัดหนึ่งมีเมือง N เมือง หมายเลข 1 ถึง N มีถนนเก่าที่ใช้ได้อยู่แล้ว K เส้น แต่ยังมีบางเมืองที่ไปมาหากันไม่ได้ วิศวกรเสนอแนวถนนใหม่ M แนว แนวที่ i เชื่อมเมือง a_i กับ b_i ราคา c_i ล้านบาท ถนนทุกเส้นวิ่งได้สองทาง

บริษัทแห่งหนึ่งรับเป็นผู้สนับสนุน จะจ่ายค่าก่อสร้างให้ถนนใหม่หนึ่งแนวที่จังหวัดเลือก จังหวัดต้องเลือกสร้างถนนใหม่บางแนว และเลือกว่าจะให้บริษัทจ่ายแนวไหน ให้ทุกเมืองไปมาหากันได้ผ่านถนนเก่าและถนนใหม่ โดยเงินที่จังหวัดต้องจ่ายเองน้อยที่สุด แนวที่บริษัทจ่ายต้องเป็นแนวที่สร้างจริง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N K และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000, 0 ≤ K ≤ 200000 และ 0 ≤ M ≤ 200000

อีก K บรรทัดเป็นถนนเก่า บรรทัดละสองจำนวน คือเมืองสองเมืองที่ถนนเชื่อม

อีก M บรรทัดเป็นแนวถนนใหม่ บรรทัดที่ i มี a_i b_i และ c_i โดยที่ 1 ≤ c_i ≤ 10⁹

ทุกถนนเชื่อมเมืองสองเมืองที่ต่างกัน และเมืองคู่เดียวกันอาจมีถนนหลายเส้น

ข้อมูลออก

เงินที่จังหวัดต้องจ่ายเองน้อยที่สุด เป็นล้านบาท ถ้าถนนเก่าต่อทุกเมืองถึงกันอยู่แล้ว ไม่ต้องสร้างอะไรเลย ให้พิมพ์ 0 ถ้าสร้างทุกแนวแล้วก็ยังไม่ครบ ให้พิมพ์ -1

ดูคำใบ้

ถนนเก่าคือเส้นราคา 0 ที่ต้องใช้แน่นอน รวมกลุ่มตามถนนเก่าให้หมดก่อน แล้วทำ Kruskal กับแนวถนนใหม่ ตรวจว่าครบด้วยจำนวนกลุ่ม เพราะถนนเก่าอาจเป็นวงจรกันเอง ส่วนผู้สนับสนุน ถ้าบริษัทจ่ายแนว e ก็เหมือน e ราคา 0 ลองทุกแนวแล้วทำ Kruskal ใหม่ทุกครั้งได้คำตอบถูก แต่เป็น O(M(N + M)) ไม่ทันเมื่อมีสองแสนแนว ลองคิดว่าเมื่อ e ราคา 0 แล้ว ต้นไม้ที่ถูกที่สุดเปลี่ยนจากเดิมได้อย่างไร ใช้การแลกเส้นแบบในข้อพิสูจน์ของ Kruskal แล้วจะเห็นว่าราคาลดได้ไม่เกินราคาของแนวที่แพงที่สุดในบรรดาแนวที่ Kruskal หยิบ ระวังกรณีไม่ต้องสร้างแนวใหม่เลย และราคารวมถึงราว 10¹⁴ ต้องใช้ long long

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    int groups = n;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        if (unite(a, b)) {
            groups--;
        }
    }
    vector<tuple<int, int, int>> roads(m);
    for (int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        roads[i] = {cost, a, b};
    }
    sort(roads.begin(), roads.end());
    long long total = 0;
    int most = 0;
    for (auto [cost, a, b] : roads) {
        if (unite(a, b)) {
            groups--;
            total += cost;
            most = max(most, cost);
        }
    }
    if (groups == 1) {
        cout << total - most << '\n';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}

ข้อ 6 วันที่แต่ละเมืองถึงศาลากลาง

ระดับกลาง เวลาไม่เกิน 1 วินาที

ภาคใต้มีเมือง N เมือง หมายเลข 1 ถึง N เมือง 1 เป็นที่ตั้งศาลากลางจังหวัด หลังน้ำท่วมใหญ่ ถนนทุกเส้นขาดหมด กรมทางหลวงซ่อมถนน M เส้น เส้นที่ i เชื่อมเมือง a_i กับ b_i และเปิดใช้ได้ตั้งแต่วันที่ d_i หลังน้ำลด ถนนทุกเส้นวิ่งได้สองทาง

ทุกเมืองต้องส่งรถไปรับถุงยังชีพที่ศาลากลาง ให้หาว่าแต่ละเมืองขับรถไปถึงเมือง 1 ได้ครั้งแรกในวันไหน โดยใช้เฉพาะถนนที่เปิดแล้ว จะผ่านกี่เมืองก็ได้

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000 และ 1 ≤ M ≤ 200000

อีก M บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i b_i และ d_i คั่นด้วยช่องว่าง โดยที่ 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i และ 1 ≤ d_i ≤ 10⁹ ถนนหลายเส้นอาจเปิดวันเดียวกัน

ข้อมูลออก

บรรทัดเดียว มีจำนวนเต็ม N - 1 จำนวน คั่นด้วยช่องว่าง จำนวนที่ i คือวันแรกที่เมือง i + 1 ไปถึงเมือง 1 ได้ ถ้าซ่อมครบทุกเส้นแล้วก็ยังไปไม่ถึง ให้เป็น -1

4 6 6 9

1 -1 -1

ดูคำใบ้

เมือง v ถึงเมือง 1 ในวัน d ได้เมื่อมีทางที่ทุกถนนเปิดภายในวัน d คำตอบของ v จึงเป็นค่าที่น้อยที่สุดของวันเปิดที่ช้าที่สุดบนทาง ถ้าเปิดถนนตามลำดับวันแล้วรวมกลุ่มแบบ Kruskal ถนนที่รวมกลุ่มได้จริงต่อกันเป็นต้นไม้ และทางจาก v ไป 1 บนต้นไม้นี้คือทางที่ดีที่สุดพอดี เหตุผลเดียวกับเรื่องรถบรรทุกที่หนักที่สุด แค่กลับทิศของการเรียง เก็บต้นไม้นี้เป็น adjacency list แล้ว BFS จากเมือง 1 ครั้งเดียว ค่าของเมืองลูกคือค่าที่มากกว่าระหว่างค่าของเมืองพ่อกับวันเปิดของถนนที่เชื่อม ระวังต้นไม้ที่เป็นสายยาวแสนเมือง DFS แบบ recursion จะพังด้วย stack overflow ถ้า BFS จากเมือง 1 ใหม่ทุกวันที่มีถนนเปิด จะช้าเกินเมื่อมีถนนสองแสนเส้น

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> roads(m);
    for (int i = 0; i < m; i++) {
        int a, b, day;
        cin >> a >> b >> day;
        roads[i] = {day, a, b};
    }
    sort(roads.begin(), roads.end());
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    vector<vector<pair<int, int>>> tree(n + 1);
    for (auto [day, a, b] : roads) {
        if (unite(a, b)) {
            tree[a].push_back({b, day});
            tree[b].push_back({a, day});
        }
    }
    vector<int> first_day(n + 1, -1);
    first_day[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto [to, day] : tree[v]) {
            if (first_day[to] == -1) {
                first_day[to] = max(first_day[v], day);
                q.push(to);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << first_day[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

ข้อ 7 รถบรรทุกข้ามสะพาน

ระดับยาก เวลาไม่เกิน 1 วินาที

บริษัทขนส่งมีเมือง N เมือง หมายเลข 1 ถึง N และถนน M เส้น ถนนเส้นที่ i เชื่อมเมือง a_i กับ b_i วิ่งได้สองทาง และมีสะพานที่รับน้ำหนักได้ไม่เกิน w_i ตัน รถคันหนึ่งวิ่งผ่านถนนเส้นใดได้ก็ต่อเมื่อน้ำหนักรถไม่เกินที่สะพานของถนนเส้นนั้นรับได้

ฝ่ายวางแผนมีคำถาม Q ข้อ ข้อที่ j ถามว่ารถหนัก t_j ตัน วิ่งจากเมือง x_j ไปเมือง y_j ได้หรือไม่ ผ่านเมืองอื่นกี่เมืองก็ได้ ถ้าเมืองต้นทางกับปลายทางเป็นเมืองเดียวกัน ถือว่าไปได้เสมอ

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N M และ Q คั่นด้วยช่องว่าง โดยที่ 2 ≤ N ≤ 100000, 1 ≤ M ≤ 200000 และ 1 ≤ Q ≤ 100000

อีก M บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i b_i และ w_i โดยที่ a_i ≠ b_i และ 1 ≤ w_i ≤ 10⁹

อีก Q บรรทัด บรรทัดที่ j มีจำนวนเต็ม x_j y_j และ t_j โดยที่ 1 ≤ x_j, y_j ≤ N และ 1 ≤ t_j ≤ 10⁹

ข้อมูลออก

Q บรรทัด ตอบตามลำดับคำถาม บรรทัดละหนึ่งข้อ พิมพ์ YES ถ้ารถวิ่งไปได้ หรือ NO ถ้าไปไม่ได้

YES
NO
YES
YES
YES
YES

ดูคำใบ้

รถหนัก t ผ่านได้เฉพาะถนนที่รับได้อย่างน้อย t ถ้าเรียงคำถามจากรถหนักไปเบา ถนนที่ใช้ได้มีแต่เพิ่มขึ้น ไม่เคยหายไป จึงเปิดถนนจากรับได้มากไปน้อยแบบรถบรรทุกในหน้า 29.5 ก่อนตอบคำถามที่หนัก t ให้เปิดถนนทุกเส้นที่รับได้ตั้งแต่ t ขึ้นไป แล้วดูว่า a กับ b อยู่กลุ่มเดียวกันไหม เก็บคำตอบตามหมายเลขคำถามแล้วพิมพ์ตามลำดับเดิม ถนนที่รับได้เท่ากับ t พอดีก็ผ่านได้ ถ้า BFS ใหม่ทุกคำถาม จะเป็น O(Q(N + M)) ซึ่งไม่ทัน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

void unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, int>> roads(m);
    for (int i = 0; i < m; i++) {
        int a, b, limit;
        cin >> a >> b >> limit;
        roads[i] = {limit, a, b};
    }
    sort(roads.begin(), roads.end(), greater<tuple<int, int, int>>());
    vector<int> from(q), to(q), weight(q), order(q);
    for (int j = 0; j < q; j++) {
        cin >> from[j] >> to[j] >> weight[j];
        order[j] = j;
    }
    sort(order.begin(), order.end(), [&](int x, int y) {
        return weight[x] > weight[y];
    });
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    vector<bool> answer(q);
    int next_road = 0;
    for (int j : order) {
        while (next_road < m && get<0>(roads[next_road]) >= weight[j]) {
            unite(get<1>(roads[next_road]), get<2>(roads[next_road]));
            next_road++;
        }
        answer[j] = find_root(from[j]) == find_root(to[j]);
    }
    for (int j = 0; j < q; j++) {
        cout << (answer[j] ? "YES" : "NO") << '\n';
    }
    return 0;
}

ข้อ 8 ไฟฟ้าทุกบ้าน

ระดับยาก เวลาไม่เกิน 1 วินาที

หมู่บ้านบนเกาะห่างไกลยังไม่มีไฟฟ้า บ้าน N หลัง หมายเลข 1 ถึง N บ้านหลังที่ i ตั้งอยู่ที่พิกัด (x_i, y_i) บนแผนที่หน่วยเมตร ทุกบ้านต้องมีไฟฟ้าใช้ ทำได้สองทาง

ติดแผงโซลาร์เซลล์ที่บ้านหลังที่ i ราคา s_i บาท
เดินสายไฟระหว่างบ้านสองหลัง i กับ j สายต้องเดินตามคันนาที่เป็นตารางตั้งฉาก ยาว |x_i - x_j| + |y_i - y_j| เมตร ราคาเมตรละ K บาท ไฟไหลในสายได้ทั้งสองทาง

บ้านหลังหนึ่งมีไฟใช้ถ้าติดแผงเอง หรือเดินสายต่อกันเป็นทอดๆ ไปถึงบ้านที่ติดแผงได้ ให้หาราคารวมที่น้อยที่สุดที่ทำให้ทุกบ้านมีไฟใช้

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 7000 และ 1 ≤ K ≤ 1000

อีก N บรรทัด บรรทัดที่ i มีจำนวนเต็ม x_i y_i และ s_i คั่นด้วยช่องว่าง โดยที่ 0 ≤ x_i, y_i ≤ 10⁶ และ 1 ≤ s_i ≤ 10⁹ บ้านหลายหลังอาจอยู่พิกัดเดียวกันได้

ข้อมูลออก

ราคารวมที่น้อยที่สุด

ดูคำใบ้

สร้างโหนดสมมติแทนแสงแดดแบบหน้า 29.5 ติดแผงที่บ้าน i คือเส้นจากโหนดสมมติไปบ้าน i ราคา s_i ทุกคู่บ้านเดินสายถึงกันได้ กราฟมีเส้นราว 24.5 ล้านเส้นเมื่อ N = 7000 ใช้ Prim แบบ O(N²) ในหน้า 29.4 ที่ไม่เก็บเส้นเชื่อม เริ่มจากต้นไม้ที่มีแค่โหนดสมมติ ค่าเริ่มต้นของ best[i] จึงเป็น s_i ราคาสายเส้นเดียวสูงสุด 2 × 10⁹ ยังอยู่ใน int แต่ราคารวมถึงราว 7 × 10¹² เกิน int ต้องเก็บด้วย long long ถ้าสร้างเส้นทุกคู่แล้วทำ Kruskal จะทั้งช้าและกินหน่วยความจำหลายร้อย MB

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long per_meter;
    cin >> n >> per_meter;
    vector<long long> x(n), y(n), best(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> best[i];
    }
    vector<bool> in_tree(n, false);
    long long total = 0;
    for (int step = 0; step < n; step++) {
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!in_tree[i] && (v == -1 || best[i] < best[v])) {
                v = i;
            }
        }
        in_tree[v] = true;
        total += best[v];
        for (int i = 0; i < n; i++) {
            if (!in_tree[i]) {
                long long cable = per_meter * (abs(x[v] - x[i]) + abs(y[v] - y[i]));
                best[i] = min(best[i], cable);
            }
        }
    }
    cout << total << '\n';
    return 0;
}