제출 #1359408

#제출 시각아이디문제언어결과실행 시간메모리
1359408eradaxDrivers (BOI24_drivers)C++20
100 / 100
222 ms69280 KiB
// Drivers
// https://oj.uz/problem/view/BOI24_drivers

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct UF{
    vector<int> e;
    UF(int n):e(n,-1){}
    int f(int x){return e[x]<0?x:e[x]=f(e[x]);}
    int u(int a,int b){
        a=f(a),b=f(b);
        if(a==b)return 0;
        if(e[a]>e[b])swap(a,b);
        e[a]+=e[b];
        e[b]=a;
        return 1;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n,m,q;cin>>n>>m>>q;
    vector<array<int,3>> edg(m);
    vector<vector<pair<int,int>>> adj(n);
    for(auto&[i,j,k]:edg)cin>>j>>k>>i,j--,k--;
    sort(begin(edg),end(edg));

    UF uf(n);
    for(auto[i,j,k]:edg)if(uf.u(j,k)){
        adj[j].push_back({k,i});
        adj[k].push_back({j,i});
    }

    const int L=20;
    vector<int> dep(n,-1);
    vector<vector<int>> up(n,vector<int>(L));
    vector<vector<int>> um(n,vector<int>(L));
    auto dfs=[&](auto&& dfs,int u,int p,int v, int d) -> void {
        dep[u]=d;
        up[u][0]=p;
        um[u][0]=v;
        for(int i=1;i<L;i++){
            up[u][i]=up[up[u][i-1]][i-1];
            um[u][i]=max(um[u][i-1],um[up[u][i-1]][i-1]);
        }

        for(auto[v,w]:adj[u])if(v!=p)dfs(dfs,v,u,w,d+1);
    };
    for(int i=0;i<n;i++)if(dep[i]==-1)dfs(dfs,i,i,0,0);

    auto query=[&](int a,int b){
        int v=0;
        if(dep[a]<dep[b])swap(a,b);
        for(int i=L-1;i>=0;i--)if(dep[up[a][i]]>=dep[b])v=max(v,um[a][i]),a=up[a][i];
        if(a==b)return v;
        for(int i=L-1;i>=0;i--)if(up[a][i]!=up[b][i])v=max({v,um[a][i],um[b][i]}),a=up[a][i],b=up[b][i];
        return max({v,um[a][0],um[b][0]});
    };

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

        if(uf.f(a)==uf.f(b)&&query(a,b)<=p){
            cout<<"TAIP\n";
        }else{
            cout<<"NE\n";
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…