제출 #1323889

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


#define int long long
#define fastcin() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'

const int N = 200007;
const int LOG = 20;


vector<pair<int, int>> g[N];
int up[N][LOG];
int mx[N][LOG];
int depth[N];
int comp[N];
bool visited[N];

void dfs(int u, int p, int w, int d, int c) {
    visited[u] = true;
    comp[u] = c;
    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 : g[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (v != p) {
            dfs(v, u, weight, d + 1, c);
        }
    }
}

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];
        }
    }

    
    res = max({res, mx[u][0], mx[v][0]});
    return res;
}

void solve() {
    int n, m, q;
    cin>>n>>m>>q;

    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 current_cc = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            current_cc++;
            
            dfs(i, i, 0, 1, current_cc);
        }
    }

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

        if (comp[a] != comp[b]) {
            cout << "NE" << endl;
            continue;
        }

        int max_edge = query_max(a, b);
        
        // If the heaviest edge on the unique tree path is less than p
        if (max_edge < p) {
            cout << "TAIP" << endl;
        } else {
            cout << "NE" << endl;
        }
    }
}

int32_t main() {
    fastcin();
    solve();
    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...