TLE70分求调!
查看原帖
TLE70分求调!
742017
zhangxiao666楼主2024/3/16 21:57
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
struct stu {int op, x, y;} q[N];
int ls[N], fa[N];

int read()
{
    int f = 1, s = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
    return f * s;
}

bool cmp(stu a1, stu a2) {return a1.op > a2.op;}

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

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}

void init()
{
    sort(ls + 1, ls + 2 * n + 1);
    int m = unique(ls + 1, ls + 2 * n + 1) - ls;
    for (int i = 1; i <= n; i++)
    {
        q[i].x = lower_bound(ls + 1, ls + m + 1, q[i].x) - ls;
        q[i].y = lower_bound(ls + 1, ls + m + 1, q[i].y) - ls;
    }
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
}

void work()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        q[i].x = read(), q[i].y = read(), q[i].op = read();
        ls[i] = q[i].x, ls[n + i] = q[i].y;
    }
    init(); sort(q + 1, q + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        if (q[i].op) merge(q[i].x, q[i].y);
        else 
        {
            if (find(q[i].x) == find(q[i].y)) 
            {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}

signed main()
{
    int T = read();
    while (T--) work();
    return 0;
}
2024/3/16 21:57
加载中...