第 2 个点 RE, 第 9, 10 个点 TLE(2.2 s), 我就是用的并查集+离散化. 是哪一步效率低于正常解呢? 以及为啥第 2 个 RE 呢? 我看第 2 个点 n <=10, 那应该不是数组开小了, 但我离散化了的呀.

#include <cstdio>
#include <cassert>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<int, int> ct; // contraint

const int SIZE = 100002;
ct equal_[SIZE];
ct unequal[SIZE];
int equal_num, unequal_num;
int fa[SIZE];

int get_id(int tar, const vector<int>& a) {
  int l = 0;
  int r = a.size() - 1;
  int mid;
  while(l<r) {
    mid = (l+r)>>1;
    if(a[mid]==tar) {
      return mid;
    } else if(a[mid]>tar) {
      r = mid - 1;
    } else {
      l = l+1;
    }
  }
  return l;
}

void init_fa(int size) {
  for(int i= 0; i < size; i++) {
    fa[i] = i;
  }
}

int get(int id) {
  if(fa[id]==id) {
    return id;
  } else {
    return fa[id]=get(fa[id]);
  }
}

void merge(int a, int b) {
  int root_a = get(a);
  int root_b = get(b);
  fa[root_a] = root_b;
}

int main() {
  freopen("input.txt", "r", stdin);
  int t;
  scanf("%d", &t);
  for(int case_id = 0; case_id < t; case_id++) {
    // equal, unequal 没必要清空
    equal_num = 0;
    unequal_num = 0;
    int n;
    scanf("%d", &n);
    int a, b, isequal; // 读入使用
    vector<int> v;
    v.reserve(SIZE<<1);
    for(int i = 0; i < n; i++) {
      scanf("%d %d %d", &a, &b, &isequal);
      v.push_back(a);
      v.push_back(b);
      if(isequal) {
        equal_[equal_num++] = pair{a,b};
      } else {
        unequal[unequal_num++] = pair{a,b};
      }
    }
    // 离散化
    std::sort(v.begin(), v.end());
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    // 初始化 fa 
    init_fa(v.size());
    // 合并相等的
    for(int i = 0; i < equal_num; i++) {
      a = equal_[i].first;
      a = get_id(a, v);
      b = equal_[i].second;
      b = get_id(b, v);
      merge(a,b);
    }
    // 检查不等的
    bool ans = true;
    for(int i = 0; i < unequal_num; i++) {
      a = unequal[i].first;
      a = get_id(a, v);
      b = unequal[i].second;
      b = get_id(b, v);
      if(get(a)==get(b)) {
        ans = false;
        break;
      }
    }
    if(ans) {
      puts("YES");
    } else {
      puts("NO");
    }
  }
  
  return 0;
}