제출 #1323896

#제출 시각아이디문제언어결과실행 시간메모리
1323896raqin_shahrierDrivers (BOI24_drivers)C++20
0 / 100
941 ms1114112 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Edge {
    int to, weight;
};

vector<Edge> adj[MAXN];
int up[MAXN][LOG], mx[MAXN][LOG], depth[MAXN];
int root_id[MAXN]; // To check if u and v are in the same tree

// DFS to precompute jump tables and label components
void dfs(int u, int p, int w, int d, int r) {
    depth[u] = d;
    root_id[u] = r;
    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, r);
        }
    }
}

int query_max(int u, int v) {
    // If they aren't in the same tree, no path exists
    if (root_id[u] != root_id[v]) return -1; 

    if (depth[u] < depth[v]) swap(u, v);

    int res = 0;
    // 1. Lift u to the same depth as v
    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;

    // 2. Lift both until they are just below the LCA
    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];
        }
    }

    // 3. Final jump to the LCA
    return max({res, mx[u][0], mx[v][0]});
}

int main() {
    // Fast I/O is important for large query counts
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, U;
    if (!(cin >> N >> M >> U)) return 0;

    for (int i = 0; i < M; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        adj[u].push_back({v, t});
        adj[v].push_back({u, t});
    }

    // Process every component in the forest
    for (int i = 1; i <= N; i++) {
        if (depth[i] == 0) {
            dfs(i, i, 0, 1, i); // Use current node 'i' as the root ID
        }
    }

    while (U--) {
        int a, b, p;
        cin >> a >> b >> p;
        int max_weight = query_max(a, b);

        if (max_weight == -1 || max_weight > p) {
            cout << "NE\n";
        } else {
            cout << "TAIP\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...