90分,测试点2MLE
查看原帖
90分,测试点2MLE
1215243
ruobanibizuoge楼主2024/7/9 08:49
#include<bits/stdc++.h>
using namespace std;
#define M (100005)

struct opt{
    int x, y, e;
} nn[M];

int t, n;
int num[M];
int cnt[M];

int fast_read() {
    int flag = 1;
    char c = ' ';
    while ((c<'0'||c>'9')&&c!='-') {  // 去除非数字字符
        c = getchar();
        if (c=='-') {  // 读到负号时,再读入一个数字
            flag = -1;
            c = getchar();
        }  // 没读到符号说明读到了数字,就不用再读
    }
    int x = 0;
    while (c>='0'&&c<='9') {
        x = 10*x + c-'0';
        c = getchar();
    }
    return x*flag;
}

int find(int x) {
    return x==num[x] ? x:num[x] = find(num[x]);
}

bool cmp(opt a, opt b) {
    return a.e > b.e;
}

int main() {
    t = fast_read();
    while(t--) {
        int tot = 0;
        n = fast_read();
        for (int i = 0; i < n; i++) {
            nn[i].x = fast_read();nn[i].y = fast_read();nn[i].e = fast_read();
            cnt[tot++] = nn[i].x; cnt[tot++] = nn[i].y;
        }
        sort(cnt, cnt+tot);
        int len = unique(cnt, cnt+tot) - cnt;
        for (int i = 0; i < n; i++) {
            nn[i].x = lower_bound(cnt, cnt+len, nn[i].x) - cnt;
            nn[i].y = lower_bound(cnt, cnt+len, nn[i].y) - cnt;
        }
        for (int i = 0; i < len; i++) {
            num[i] = i;
        }
        sort(nn, nn+n, cmp);
        int flag = 1;
        for (int i = 0; i < n; i++) {
            int f1 = find(nn[i].x), f2 = find(nn[i].y);
            if (nn[i].e == 1) {
                if (f1 != f2) num[f1] = f2;
            }
            else {
                if (f1 == f2) {
                    flag = 0;
                    break;
                }
            }
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
2024/7/9 08:49
加载中...