Submission #1323900

#TimeUsernameProblemLanguageResultExecution timeMemory
1323900raqin_shahrierDrivers (BOI24_drivers)C++20
0 / 100
0 ms332 KiB
#include <iostream>
#include <algorithm>

using namespace std;

// Tighten constants to save every kilobyte
const int MAXN = 100005;
const int MAXM = 200005; // 2 * edges for two-way roads
const int LOG = 17; 

// Static Adjacency List (Uses much less memory than vector)
int head[MAXN], to[MAXM], nxt[MAXM], wt[MAXM], edge_cnt = 0;
void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    wt[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// Binary Lifting Tables
int up[MAXN][LOG];
int mx[MAXN][LOG];
int depth[MAXN];
int root_id[MAXN];

// Simple Queue for Iterative BFS (BFS is easier for memory than iterative DFS)
int q[MAXN];

void bfs(int start_node) {
    int l = 0, r = 0;
    q[r++] = start_node;
    depth[start_node] = 1;
    root_id[start_node] = start_node;
    up[start_node][0] = start_node;
    mx[start_node][0] = 0;

    while (l < r) {
        int u = q[l++];
        
        // Precompute jump table for this node
        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 (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (v != up[u][0]) {
                depth[v] = depth[u] + 1;
                root_id[v] = start_node;
                up[v][0] = u;
                mx[v][0] = wt[i];
                q[r++] = v;
            }
        }
    }
}

int query_max(int u, int v) {
    if (root_id[u] != root_id[v]) return 2e9 + 7;
    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() {
    // Fast I/O
    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;
        add_edge(u, v, t);
        add_edge(v, u, t);
    }

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

    while (U--) {
        int a, b, p;
        cin >> a >> b >> p;
        if (query_max(a, b) <= p) cout << "Yes\n";
        else cout << "No\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...