Submission #1332079

#TimeUsernameProblemLanguageResultExecution timeMemory
1332079snowavenodeDrivers (BOI24_drivers)C++20
100 / 100
244 ms15912 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<tuple<ll, ll, ll>> edges;
vector<int> dsu, sz;

struct Queries {
    ll t; int a, b, idx; bool res;
};

vector<Queries> queries;

int find(int x) {
    while(dsu[x] != x) {
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}

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

    int n, m, q; cin >> n >> m >> q;
    dsu.resize(n + 1); sz.resize(n + 1);
    for(int i = 1; i <= n; i++) {dsu[i] = i; sz[i] = 1;}
    for(int i = 1; i <= m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        edges.push_back({w, u, v});
    }
    sort(edges.begin(), edges.end());

    for(int i = 1; i <= q; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        queries.push_back({w, u, v, i, 0});
    }
    sort(queries.begin(), queries.end(), [](auto &a, auto &b) {
        return a.t < b.t;
    });

    int idx = 0;
    for(int i = 0; i < q; i++) {
        auto [t, a, b, _, _2] = queries[i];
        while(idx < m && get<0>(edges[idx]) <= t) {
            auto [w, u, v] = edges[idx];
            u = find(u); v = find(v);
            if(u != v) {
                if(sz[u] < sz[v]) swap(u, v);
                dsu[v] = u;
                sz[u] += sz[v];
            }
            idx++;
        }
        queries[i].res = find(a) == find(b) ? 1 : 0;
    }

    sort(queries.begin(), queries.end(), [](auto &a, auto &b) {
        return a.idx < b.idx;
    });

    for(auto &e : queries) {
        if(e.res) cout << "TAIP";
        else cout << "NE";
        cout << endl;
    }

    return 0;
}
#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...