Submission #1220743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220743		s3yoonpark	Drivers (BOI24_drivers)	C++20	100 / 100	247 ms	60864 KiB

Main

#include <bits/stdc++.h>
#define ll long long 
#define ar array
#define sz(x) (int)(x).size()  
using namespace std; 

struct DSU {
  int n; 
  vector<int> rep, siz; 
  DSU (int ss) {
    n = ss; 
    rep.assign(n + 1, 0);
    siz.assign(n + 1, 0); 
    iota(rep.begin(), rep.end(), 0); 
    fill(siz.begin(), siz.end(), 1); 
  }
  int findRep(int x) {
    if (rep[x] == x) return x; 
    return rep[x] = findRep(rep[x]); 
  }
  bool unite(int u, int v) {
    int repU = findRep(u), repV = findRep(v); 
    if (repU == repV) return false; 
    if (siz[u] < siz[v]) swap(u, v); 
    siz[u] += siz[v]; 
    rep[repV] = repU; 
    return true; 
  }
}; 

void solve() {
  int N, M, U; cin >> N >> M >> U; 
  DSU dsu(N); 
  vector<ar<int,3>> edges; 
  vector adj(N + 1, vector<ar<int,2>>{}); 
  vector par(N + 1, N + 1); 
  vector parEdge(N + 1, -1); 
  vector depth(N + 1, 1); 
  while (M--) {
    int x, y, t; 
    cin >> x >> y >> t; 
    edges.push_back({t, x, y}); 
  }
  for (int i = 1; i + 1 <= N; i++) {
    edges.push_back({(int)2E9, i, i + 1}); 
  }
  sort(edges.begin(), edges.end()); 
  for (auto &[t, x, y] : edges) {
    if (dsu.unite(x, y)) {
      adj[x].push_back({y, t}); 
      adj[y].push_back({x, t}); 
    }
  }
  auto dfs = [&] (auto self, int u, int p) -> void {
    for (auto &[v, w] : adj[u]) {
      if (v == p) continue;
      par[v] = u; 
      parEdge[v] = w; 
      depth[v] = depth[u] + 1; 
      self(self, v, u); 
    }
  }; 
  dfs(dfs, 1, -1); 
  vector maxEdge(19, vector(N + 2, 0)); 
  vector tp(19, vector(N + 2, N + 1)); 
  for (int i = 0; i < 19; i++) {
    for (int j = 1; j <= N; j++) {
      if (i == 0) {
        maxEdge[i][j] = parEdge[j]; 
        tp[i][j] = par[j]; 
      } else {
        maxEdge[i][j] = max(maxEdge[i - 1][j], maxEdge[i - 1][tp[i - 1][j]]); 
        tp[i][j] = tp[i - 1][tp[i - 1][j]]; 
      }
    }
  }
  auto jump = [&] (int u, int step) -> int {
    for (int i = 0; i <= 18; i++) {
      if ((1 << i) & step) {
        u = tp[i][u]; 
      }
    }
    return u; 
  }; 
  auto findLca = [&] (int u, int v) -> int {
    if (depth[u] > depth[v]) swap(u, v); 
    v = jump(v, depth[v] - depth[u]); 
    if (u == v) return u; 
    for (int i = 18; i >= 0; i--) {
      if (tp[i][v] != tp[i][u]) {
        v = tp[i][v], u = tp[i][u]; 
      }
    }
    return tp[0][v]; 
  }; 
  auto findMaxEdge = [&] (int u, int v) -> int {
    int lca = findLca(u, v); 
    int ans = 0; 
    for (int i = 18; i >= 0; i--) {
      if (depth[u] - (1 << i) >= depth[lca]) {
        ans = max(ans, maxEdge[i][u]); 
        u = tp[i][u]; 
      }
    }
    for (int i = 18; i >= 0; i--) {
      if (depth[v] - (1 << i) >= depth[lca]) {
        ans = max(ans, maxEdge[i][v]); 
        v = tp[i][v]; 
      }
    }
    return ans; 
  }; 
  while (U--) { 
    int a, b, p; cin >> a >> b >> p; 
    int mx = findMaxEdge(a, b); 
    cout << (p >= mx ? "TAIP\n" : "NE\n"); 
  }
}
 
int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr); 
  int tests = 1; 
  // cin >> tests; 
  while (tests--) solve(); 
  return 0; 
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45