Submission #1364600

#TimeUsernameProblemLanguageResultExecution timeMemory
1364600norrawichzzzDrivers (BOI24_drivers)C++20
100 / 100
213 ms69700 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+5, LOG = 20;
int val[N], up[LOG][N], depth[N];
vector<vector<int>> adj(N);

void dfs(int u) {
    for (auto &v : adj[u]) {
        up[0][v] = u;
        depth[v] = depth[u]+1;
        for (int i=1; i<LOG; i++) up[i][v] = up[i-1][up[i-1][v]];
        dfs(v);
    }
}

int fnd(int u, vector<int> &par) {
    if (par[u]==u) return u;
    return par[u] = fnd(par[u], par);
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a,b);

    int diff = depth[b]-depth[a];
    for (int i=LOG-1; i>=0; i--) {
        if (diff&(1<<i)) {
            b=up[i][b];
        }
    }

    if (a==b) return a;

    for (int i=LOG-1; i>=0; i--) {
        if (up[i][a] != up[i][b]) {
            a=up[i][a];
            b=up[i][b];
        }
    }
    return up[0][a];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,q;
    cin>> n>> m>> q;

    vector<tuple<int,int,int>> edge;
    for (int i=0; i<m; i++) {
        int u,v,w;
        cin>> u>> v>> w;
        edge.push_back({w,u,v});
    }

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

    sort(edge.begin(), edge.end());

    int cnt=n+1;
    for (auto [w,u,v] : edge) {
        int a=fnd(u, par);
        int b=fnd(v, par);

        if (a!=b) {
           // cout<< cnt<< ' '<< a<< ' '<< b<< '\n';
            par[a] = cnt;
            par[b] = cnt;
            adj[cnt].push_back(a);
            adj[cnt].push_back(b);
            val[cnt] = w;
            cnt++;
        }
    }
    set<int> root;
    for (int i=1; i<=n; i++) {
        int a = fnd(i, par);
        //cout<< a<< ' ';
        if (!root.count(a)) root.insert(a);
    }

    for (auto &r : root) dfs(r);

    while (q--) {
        int a,b,p;
        cin>> a>> b>> p;

        if (fnd(a, par) != fnd(b, par)) cout<< "NE\n";
        else {
            int LCA = lca(a,b);
            //cout<< "maybe\n";
            if (val[LCA] <= p) cout<< "TAIP\n";
            else cout<< "NE\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...