Submission #1358866

#TimeUsernameProblemLanguageResultExecution timeMemory
1358866backer8002Drivers (BOI24_drivers)C++20
0 / 100
1 ms580 KiB
#include<bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> edges;
constexpr int Log = 20;

int tin[200000],tout[200000],depth[200000];
pair<int,int> jumptable[Log][200000];

void BFS(int cur,int prev,int weight,int d) {
    static int t = 0;

    tin[cur] = ++t;

    jumptable[0][cur] = {prev,weight};
    depth[cur] = d;

    for (int i = 1; i < Log; i++) {
        jumptable[i][cur].first = jumptable[jumptable[i-1][cur].first][i-1].first;
        jumptable[i][cur].second = max(jumptable[jumptable[i-1][cur].first][i-1].second,jumptable[i-1][cur].second);
    }

    for (auto[edge,w] : edges[cur]) if (edge != prev) BFS(edge,cur,w,d+1);

    tout[cur] = ++t;
}

int main() {
    int N,M,U;
    cin >> N >> M >> U;

    vector<array<int,3>> things(M);
    for (auto& thing : things)
        cin >> thing[0] >> thing[1] >> thing[2], thing[0]--,thing[1]--;

    sort(things.begin(),things.end(),[](const auto& f, const auto& s) {
        return f[2] < s[2];
    });

    vector<int> unionfind(N);
    for (int i = 0; i < N; i++)
        unionfind[i] = i;

    auto FindUnion = [&unionfind](int onion) {
        while (unionfind[unionfind[onion]] != unionfind[onion])
            unionfind[onion] = unionfind[unionfind[onion]];
        return unionfind[onion];
    };
    edges = vector(N,vector<pair<int,int>>());

    for (int i = 0; i < M; i++) {
        int aUnion = FindUnion(things[i][0]);
        int bUnion = FindUnion(things[i][1]);
        if (aUnion == bUnion)
            continue;

        unionfind[aUnion] = unionfind[bUnion];
        edges[things[i][0]].emplace_back(things[i][1],things[i][2]);
        edges[things[i][1]].emplace_back(things[i][0],things[i][2]);
    }

    for (int i = 0; i < N; i++) {
        if (tin[i]) continue;
        BFS(i,i,0,0);
    }

    static auto IsAns = [](int p, int c) {
        return tin[p] <= tin[c] && tin[c] <= tout[p];
    };

    static auto LCA = [](int a, int b) {
        if (IsAns(a,b))
            return a;
        if (IsAns(b,a))
            return b;
        for (int i = Log-1; i >= 0; i--) {
            if (not IsAns(jumptable[i][a].first,b))
                a = jumptable[i][a].first;
        }
        return jumptable[0][a].first;
    };

    for (int i = 0; i < U; i++) {
        int a,b,t;
        cin >> a >> b >> t;
        a--,b--;

        if (FindUnion(a) != FindUnion(b)) {
            cout << "NE\n";
            continue;
        }
        int lca = LCA(a,b);
        int maxiumum = 0;

        {
            int toJump = depth[a] - depth[lca];
            for (int i = 0; i < Log; i++) {
                if (toJump >> i & 1) {
                    maxiumum = max(maxiumum,jumptable[i][a].second);
                    a = jumptable[i][a].first;
                }
            }
        }
        {
            int toJump = depth[b] - depth[lca];
            for (int i = 0; i < Log; i++) {
                if (toJump >> i & 1) {
                    maxiumum = max(maxiumum,jumptable[i][b].second);
                    b = jumptable[i][b].first;
                }
            }
        }
        if (maxiumum > t)
            cout << "NE\n";
        else
            cout << "TAIP\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...