Submission #1359401

#TimeUsernameProblemLanguageResultExecution timeMemory
1359401haireDrivers (BOI24_drivers)C++20
100 / 100
207 ms9528 KiB
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct UF {
    vi e;
    UF(int n) : e(n, -1) {}
    bool sameSet(int a, int b) { return find(a) == find(b); }
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        e[a] += e[b]; e[b] = a;
        return true;
    }
};

int main(){
    int n,m,q;
    cin >> n >> m >> q;
    vector<tuple<int,int,int>> edges;
    vector<tuple<int,int,int,int> > queries;

    vector <int> ans(q,-1);

    rep(i,0,m){
        int a,b,c;
        cin >> a >> b >> c;
        edges.push_back({c,a,b});
    }
    rep(i,0,q){
        int a,b,c;
        cin >> a >> b >> c;
        queries.push_back({c,a,b,i});
    }


    edges.push_back({1e9+1,0,0});

    UF uf(n+1);

    sort(all(edges));
    sort(all(queries));
    reverse(all(edges));
    reverse(all(queries));

    while (sz(edges) && sz(queries)){
        if (get<0>(edges[sz(edges)-1]) <= get<0>(queries[sz(queries)-1])){
            int a,b,c;
            tie(a,b,c) = edges[sz(edges)-1];
            uf.join(b,c);
            edges.pop_back();
        }
        else{
            int a,b,c,d;
            tie(a,b,c,d) = queries[sz(queries)-1];
            queries.pop_back();
            ans[d] = (uf.find(b) == uf.find(c));
        }
    }
    rep(i,0,q){
        if (ans[i]) cout << "TAIP";
        else cout << "NE";
        cout << "\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...