제출 #1329953

#제출 시각아이디문제언어결과실행 시간메모리
1329953rewqewDrivers (BOI24_drivers)C++17
21 / 100
107 ms4772 KiB
#include <iostream>
#include <vector>
#include <algorithm>

struct road {
    int a,b,w;
    
    bool operator<(const road& other) const {
        return w < other.w;
    }

    road(int v1, int v2, int v3) {
        a = v1;
        b = v2;
        w = v3;
    }
};

struct query {
    int a, b, t, ind;
    
    bool operator<(const query& other) const {
        return t < other.t;
    }

    query(int i1, int i2, int i3, int i4) {
        a = i1;
        b = i2;
        t = i3;
        ind = i4;
    }
};



int main() {
    int n, m, u;
    std::cin >> n >> m >> u;

    std::vector<road> roads;
    for (int i = 0; i < m; i++) {
        int a,b,w;
        std::cin >> a >> b >> w;
        road r(a,b,w);
        roads.push_back(r);
    }

    std::sort(roads.begin(), roads.end());

    std::vector<int> sz(n, 1);
    std::vector<int> pa;
    for (int i = 0; i < n; i++) {
        pa.push_back(i);
    }

    auto find = [&](auto&& self, int a) -> int {
        if (a != pa[a]) {
            pa[a] = self(self, pa[a]);
        } 
        return pa[a];
    };

    auto unite = [&](int a, int b) {
        a = find(find, a);
        b = find(find, b);

        if (a == b) {
            return;
        }

        if (sz[a] < sz[b]) {
            std::swap(a,b);
        }

        pa[b] = a;
        sz[a] += sz[b];
    };

    std::vector<bool> ans(u);
    std::vector<query> queries;
    for (int i = 0; i < u; i++) {
        int a, b, t;
        std::cin >> a >> b >> t;
        queries.push_back(query(a,b,t,i));
    }

    std::sort(queries.begin(), queries.end());

    int ri = 0;
    for (query& q : queries) {
        while (roads[ri].w <= q.t && ri < m) {
            unite(roads[ri].a, roads[ri].b);
            ri++;
        }
        ans[q.ind] = (find(find, q.a) == find(find, q.b));
    }

    for (bool b : ans) {
        if (b) {
            std::cout << "TAIP\n";
        }
        else {
            std::cout << "NE\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...