Submission #1323690

#TimeUsernameProblemLanguageResultExecution timeMemory
1323690raqin_shahrierDrivers (BOI24_drivers)C++20
55 / 100
51 ms3288 KiB
#include <bits/stdc++.h>
// #include <vector>
// #include <algorithm>

using namespace std;

const int MAXN = 100005;
const int LOG = 18;

struct Edge {
    int u, v, t;
};

struct NodeEdge {
    int to, weight;
};

int parent[MAXN];
int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

vector<NodeEdge> adj[MAXN];
int up[MAXN][LOG], mx[MAXN][LOG], depth[MAXN];

void dfs(int u, int p, int w, int d) {
    depth[u] = d;
    up[u][0] = p;
    mx[u][0] = w;
    for (int i = 1; i < LOG; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        mx[u][i] = max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
    }
    for (auto& edge : adj[u]) {
        if (edge.to != p) dfs(edge.to, u, edge.weight, d + 1);
    }
}

int get_path_max(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int res = 0;
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            res = max(res, mx[u][i]);
            u = up[u][i];
        }
    }
    if (u == v) return res;
    for (int i = LOG - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            res = max({res, mx[u][i], mx[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    return max({res, mx[u][0], mx[v][0]});
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M, U;
    cin >> N >> M >> U;

    vector<Edge> edges(M);
    for (int i = 0; i < M; i++) cin >> edges[i].u >> edges[i].v >> edges[i].t;

    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.t < b.t; });
    for (int i = 1; i <= N; i++) parent[i] = i;

    int edges_count = 0;
    for (auto& e : edges) {
        int root_u = find_set(e.u);
        int root_v = find_set(e.v);
        if (root_u != root_v) {
            parent[root_u] = root_v;
            adj[e.u].push_back({e.v, e.t});
            adj[e.v].push_back({e.u, e.t});
            edges_count++;
        }
    }

    
    for (int i = 1; i <= N; i++) {
        if (depth[i] == 0) dfs(i, i, 0, 1);
    }

   
    while (U--) {
        int a, b, p;
        cin >> a >> b >> p;
        if (find_set(a) != find_set(b)) {
            
            cout << "NE" << "\n"; 
        } else {
            cout << (get_path_max(a, b) <= p ? "TAIP" : "NE") << "\n";
        }
    }

    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...