제출 #1323890

#제출 시각아이디문제언어결과실행 시간메모리
1323890raqin_shahrierDrivers (BOI24_drivers)C++20
0 / 100
2082 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

// REMOVED #define int long long to save 50% memory on arrays
// Only use long long where strictly necessary (weights/sums)
typedef long long ll;

const int N = 200005;
const int LOG = 19; // 2^18 > 200,000, 19 is enough

// Using 32-bit ints for everything except weights to stay under tight limits
int up[N][LOG];
int mx[N][LOG];
int depth[N];
int comp[N];
bool visited[N];
vector<pair<int, int>> g[N];

struct State {
    int u, p, w, d, c, edge_idx;
};

// Iterative DFS to prevent Stack Overflow / MLE from recursion
void iterative_dfs(int start_node, int component_id) {
    stack<State> st;
    st.push({start_node, start_node, 0, 1, component_id, 0});

    while (!st.empty()) {
        State& top = st.top();
        int u = top.u;
        int p = top.p;

        if (top.edge_idx == 0) {
            visited[u] = true;
            comp[u] = top.c;
            depth[u] = top.d;
            up[u][0] = p;
            mx[u][0] = top.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]);
            }
        }

        if (top.edge_idx < g[u].size()) {
            pair<int, int> edge = g[u][top.edge_idx];
            top.edge_idx++;
            if (edge.first != p) {
                st.push({edge.first, u, edge.second, top.d + 1, top.c, 0});
            }
        } else {
            st.pop();
        }
    }
}

int query_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_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    int c_id = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            c_id++;
            iterative_dfs(i, c_id);
        }
    }

    while (q--) {
        int a, b, p;
        cin >> a >> b >> p;
        if (comp[a] != comp[b]) {
            cout << "NE\n";
        } else {
            // max_edge < p means we can pass
            if (query_max(a, b) < p) cout << "TAIP\n";
            else cout << "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...