Submission #1350662

#TimeUsernameProblemLanguageResultExecution timeMemory
1350662NewtonabcDrivers (BOI24_drivers)C++20
100 / 100
212 ms60948 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int pa[N],ti,d[N][19],a[N],dep[N];
bool vs[N];
vector<int> adj[N];
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
void merge(int u,int v,int w){
    if(root(u)==root(v)) return;
    int ru=root(u),rv=root(v);
    ti++;
    a[ti]=w;
    d[ru][0]=d[rv][0]=ti;
    pa[ru]=pa[rv]=pa[ti]=ti;
    adj[ti].push_back(ru);
    adj[ti].push_back(rv);
}
void dfs(int u,int p){
    d[u][0]=p;
    vs[u]=true;
    for(auto v:adj[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=18;i>=0;i--) if(dep[d[v][i]]>=dep[u]) v=d[v][i];
    if(u==v) return u;
    for(int i=18;i>=0;i--) if(d[v][i]!=d[u][i]) u=d[u][i],v=d[v][i];
    return d[u][0];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q; cin>>n >>m >>q;
    ti=n;
    for(int i=1;i<=n;i++) pa[i]=i;
    vector<tuple<int,int,int>> edge;
    for(int i=0;i<m;i++){
        int u,v,w; cin>>u >>v >>w;
        edge.push_back({w,u,v});
    }
    sort(edge.begin(),edge.end());
    for(auto [w,u,v]:edge){
        merge(u,v,w);
    }
    for(int i=ti;i>=1;i--){
        if(!vs[i]) dfs(i,i);
    }
    for(int i=1;i<=18;i++) for(int j=1;j<=ti;j++) d[j][i]=d[d[j][i-1]][i-1];
    while(q--){
        int u,v,w; cin>>u >>v >>w;
        if(root(u)!=root(v)){
            cout<<"NE\n";
            continue;
        }
        int lc=lca(u,v);
        if(a[lc]<=w) cout<<"TAIP\n";
        else cout<<"NE\n";
    }

}
#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...