제출 #1323929

#제출 시각아이디문제언어결과실행 시간메모리
1323929raqin_shahrierDrivers (BOI24_drivers)C++20
100 / 100
243 ms96684 KiB
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// using namespace __gnu_pbds;
 
typedef long long ll;
 
#define int long long
 
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vpi vector<pair<int,int>>
#define rep(ii,st, n) for(int ii=st; ii<n; ii++)
#define gp " "

//bit_manupulation
#define checkbit(x,n) (x&(1LL<<n))
#define setbit(x,n) (x=(x|(1LL<<n)))
#define resetbit(x,n) (x=(x&(~(1LL<<n))))
#define pow2(i) (1LL<<i)
#define bitcnt(x) ((sizeof(x) <= sizeof(int)) ? (32 - __builtin_clz(x)) : (64 - __builtin_clzll(x)))

// #define DEBG

#define debug(n)
#define debugc(a)
#define debugcc(a)
#ifdef DEBG
#define debug(n) cout<<__LINE__<<gp<<#n<<gp<<n<<endl;
#define debugc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<el<<gp;}cout<<']'<<endl;
#define debugcc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<'{'<<gp<<el.ff<<','<<el.ss<<gp<<'}'<<gp;}cout<<']'<<endl;
#endif

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


#define All(a) a.begin(),a.end()
template<typename T> void get_vector(T&a){for(auto&e:a)cin>>e;}
template<typename T> void put_vector(T a){for(auto e:a)cout<<e<<" ";cout<<endl;}


const ll INF = 2e18;
const ll inf = INT_MAX;
const ll M = 1e9 + 7;
const ll N = 2e5 + 7;
const ll modinvof2 = 500000004;


//==============================CODE STARTS HERE==============================//


int parent[N], sz[N];
vector<vector<pair<int,int>>>g(N);

void make(int v){
  parent[v] = v;
  sz[v] = 1;
}

int find(int v){
  if(parent[v] == v) return parent[v];
  return parent[v] = find(parent[v]);
}

void Union(int a,int b){
  a = find(a);
  b = find(b);
  debug(a)
  debug(b)
  debug(sz[a])
  debug(sz[b])
  if(a!=b){
    if(sz[a]<sz[b]){
      swap(a,b);
    }
    parent[b] = a;
    sz[a]+=sz[b];
    
  }
}

const int LOG = 20;

int up[N][LOG], mx[N][LOG], depth[N];

void dfs(int u, int p, int w, int d){
  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 child = edge.ff;
    int wt = edge.ss;
    if(child != p){
      dfs(child,u,wt,d+1);
    }
  }
}
int find_max(int u, int v){
  if(depth[u] < depth[v]) swap(u,v);
  int tmx = 0;
  for(int  i = LOG-1; i>=0; i--){
    if(depth[u] - (1<<i) >= depth[v]){
      tmx = max(tmx, mx[u][i]);
      u = up[u][i];
    }
  }
  if(u == v) return tmx;
  for(int i = LOG-1; i>=0; i--){
    if(up[u][i] != up[v][i]){
      tmx = max({tmx, mx[u][i], mx[v][i]});
      u = up[u][i];
      v = up[v][i];
    }
  }
  return max({tmx,mx[u][0], mx[v][0]});
}



void preprocessing(){

}

void solve(int testcases){
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int,pair<int,int>>>edges;
    for(int i = 0; i<m; i++){
      int u,v,w;
      cin>>u>>v>>w;
      edges.push_back({w, {u,v}});
      
    }
    sort(edges.begin(), edges.end());
    for(int i = 1; i<=n; i++){
      make(i);
    }
    for(auto& edge: edges){
      int u = edge.ss.ff;
      int v = edge.ss.ss;
      int w = edge.ff;
      if(find(u) == find(v))continue;
      debug(u)
      debug(v)
      Union(u,v);
      g[u].push_back({v,w});
      g[v].push_back({u,w});
    }
    for(int i = 1; i<=n; i++){
      if(depth[i] == 0) dfs(i,i,0,1);
    }
    while(q--){
      int a,b,p;
      cin>>a>>b>>p;
      debug(find(a))
      if(find(a) != find(b)){
        cout<<"NE\n";
      }
      else{
        int mxe = find_max(a,b);
        debug(mxe)
        if(mxe > p){
          cout<<"NE\n";
        }
        else{
          cout<<"TAIP\n";
        }
      }
    }

}

int32_t main(){
    fastcin();

    int t=1;
    // cin>>t;
    preprocessing();
    rep(i,1,t+1){
       solve(i);
    }
    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...