Submission #1159866

#TimeUsernameProblemLanguageResultExecution timeMemory
1159866fv3Drivers (BOI24_drivers)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, pair<int, int>>> edges;
vector<int> par, sz;

int find(int index) {
    if (par[index] == index) return par[index];
    return par[index] = find(par[index]);
}

struct query {
    int d;
    int a, b;
    int i;

    bool operator<(query other) {
        return d < other.d;
    }
};

void unite(int a, int b) {
    a = par[a]; b = par[b];
    if (a == b) return;

    if (sz[a] > sz[b]) {
        swap(a, b);
    }

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, Q;
    cin >> N >> M >> Q;

    edges = vector<pair<int, pair<int, int>>>(M);

    par = vector<int>(N);
    sz = vector<int>(N, 1);
    iota(par.begin(), par.end(), 0);

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges[i] = {c, {a, b}};
    }
    sort(edges.begin(), edges.end());
    edges.push_back({(int)(1e9+7), {0, 0}});

    vector<query> queries(Q); 
    for (int q = 0; q < Q; q++) {
        int a, b, d;
        cin >> a >> b >> d;
        a--; b--;
        queries[q] = {d, a, b, q};
    }
    sort(queries.begin(), queries.end());

    vector<int> res(Q);
    int i = 0;
    for (auto q : queries) {
        while (edges[i].first <= q.d) {
            unite(edges[i].second.first, edges[i].second.second);
            i++;
        }
        if (find(q.a) == find(q.b)) {
            res[q.i] = 1;
        } 
    }

    for (auto r : res) {
        cout << (r ? "TAIP" : "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...