LibreOJ 2129 「NOI2015」程序自动分析

lyd 大佬给予蒟蒻们的人口普查题……

由于题目并没有问第一个不满足的约束条件，所以可以根据“相等”条件的传递性，先扫描所有相等的条件并把两个操作数并入一个集合。
然后扫描不等的条件，看是否已经属于同一个集合。

不过如果要求第一个不满足的可以加个二分答案。

注意离散化。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6;
int t;
int n;
vector<int> q[3],s[2];
int ind[(N << 1) + 10],tot,len;
int fa[(N << 1) + 10];
bool flag;
int get(int x)
{
    return fa[x] == x ? fa[x] : fa[x] = get(fa[x]);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag = 1,tot = 0;
        q[0].clear(),q[1].clear(),q[2].clear(),s[0].clear(),s[1].clear();
        scanf("%d",&n);
        for(register int i = 1;i <= (n << 1);++i)
            fa[i] = i;
        int x,y,z;
        for(register int i = 1;i <= n;++i)
            scanf("%d%d%d",&x,&y,&z),q[0].push_back(x),q[1].push_back(y),q[2].push_back(z),ind[++tot] = x,ind[++tot] = y;
        sort(ind + 1,ind + tot + 1);
        len = unique(ind + 1,ind + tot + 1) - ind - 1;
        for(register int i = 0;i < q[0].size();++i)
        {
            x = lower_bound(ind + 1,ind + len + 1,q[0][i]) - ind;
            y = lower_bound(ind + 1,ind + len + 1,q[1][i]) - ind;
            z = q[2][i];
            if(z)
                fa[get(x)] = get(y);
            else
                s[0].push_back(x),s[1].push_back(y);
        }
        for(register int i = 0;i < s[0].size();++i)
            if(get(s[0][i]) == get(s[1][i]))
            {
                puts("NO");
                flag = 0;
                break;
            }
        if(flag)
            puts("YES");
    }
}