Submission

Score: 100

User: syndrxme

Problemset: เดินทางข้ามชุมชน

Language: cpp

Time: 0.136 second

Submitted On: 2026-03-14 14:32:36

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 1. สร้างโครงสร้างเก็บข้อมูลถนน
struct Edge {
    int u, v, w;
    // สร้างเงื่อนไขสำหรับ sort: เรียงถนนจากความยาวน้อยไปมาก
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

// 2. สร้างโครงสร้างเก็บข้อมูลคำถาม
struct Query {
    int a, b, k, id; // id เอาไว้จำว่าคำถามนี้คือข้อที่เท่าไหร่ จะได้ตอบถูกลำดับ
    // สร้างเงื่อนไขสำหรับ sort: เรียงคำถามจากความจุน้ำมัน (k) น้อยไปมาก
    bool operator<(const Query& other) const {
        return k < other.k;
    }
};

const int MAXN = 100005; // เมืองมีสูงสุด 100,000 เมือง
int parent_node[MAXN];

// 3. ฟังก์ชันของ DSU (หาหัวหน้ากลุ่ม)
int find_set(int v) {
    if (v == parent_node[v])
        return v;
    // Path Compression: ทำให้การหาครั้งต่อไปเร็วขึ้นเป็น O(1)
    return parent_node[v] = find_set(parent_node[v]);
}

// 4. ฟังก์ชันของ DSU (รวมสองกลุ่มเข้าด้วยกัน)
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        parent_node[b] = a; // ให้ a เป็นหัวหน้าของ b
    }
}

int main() {
    // Fast I/O (สำคัญมาก เพราะข้อมูลเยอะ)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].a >> queries[i].b >> queries[i].k;
        queries[i].id = i; // จำลำดับดั้งเดิมของคำถามไว้
    }

    // 5. หัวใจของ Offline Query: Sort ถนน และ คำถาม
    sort(edges.begin(), edges.end());
    sort(queries.begin(), queries.end());

    // 6. ตั้งค่าเริ่มต้น DSU ให้แต่ละเมืองเป็นหัวหน้าของตัวเอง
    for (int i = 0; i < n; i++) {
        parent_node[i] = i;
    }

    vector<string> ans(q); // สร้าง Array เก็บคำตอบเพื่อรอไปพิมพ์ตอนจบ
    int edge_idx = 0;      // ตัวชี้ว่าตอนนี้เราเชื่อมถนนถึงเส้นที่เท่าไหร่แล้ว

    // 7. เริ่มประมวลผลคำถาม (Sweep)
    for (int i = 0; i < q; i++) {
        int current_k = queries[i].k;

        // วนลูปเชื่อมถนน "ทุกเส้นที่ความยาวไม่เกินน้ำมัน (k)" เข้ามาใน DSU
        while (edge_idx < m && edges[edge_idx].w <= current_k) {
            union_sets(edges[edge_idx].u, edges[edge_idx].v);
            edge_idx++;
        }

        // เช็กว่าเมือง a กับ b ถูกเชื่อมจนอยู่กลุ่มเดียวกันหรือยัง?
        if (find_set(queries[i].a) == find_set(queries[i].b)) {
            ans[queries[i].id] = "Yes";
        } else {
            ans[queries[i].id] = "No";
        }
    }

    // 8. พิมพ์คำตอบตามลำดับเดิม
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}