求助 90分 第二点TLE 哪里还能优化
查看原帖
求助 90分 第二点TLE 哪里还能优化
311830
Lhz1313楼主2020/9/2 10:47
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define mod 156541618464137161
using namespace std;
long int num[1000008];
map<long,long>vis;
long int a[1000008];
struct xx
{
    long int a, b, c;
} xz[1000005];
int cmp(xx x, xx y)
{
    return x.c > y.c;
}
long int fi(long int x)
{
    if(a[x]==x) return x;
    else return a[x]=fi(a[x]);
}
void join(long int x, long int y)
{
   long  int x1 = fi(x), y1 = fi(y);
    if (x1 != y1)
        a[x1] = y1;
}
using namespace std;
int main()
{
    long int n, m, x, y, z, x1, x2, mm,count=-1,l,j;
    cin >> n;
    while (n--)
    {
        cin >> m;
        mm = 0;
        while (mm < m)
        {
            cin >> xz[mm].a >> xz[mm].b >> xz[mm].c;
            if(!vis[xz[mm].a])
            {num[++count]=xz[mm].a;vis[xz[mm].a]=1;}
             if(!vis[xz[mm].b])
            {num[++count]=xz[mm].b;vis[xz[mm].b]=1;}
            mm++;
        }
        sort(num,num+count);
        for(long i=0;i<=count;i++)
        a[i]=i;
        sort(xz, xz + mm, cmp);
        mm = 0;
        while (mm < m)
        {
            if (xz[mm].c == 1)
                join(lower_bound(num,num+count,xz[mm].a)-num,lower_bound(num,num+count,xz[mm].b)-num);
            else
            {
                if (fi(lower_bound(num,num+count,xz[mm].a)-num) == fi(lower_bound(num,num+count,xz[mm].b)-num))
                {
                    cout << "NO" << endl;
                    break;
                }
            }
            mm++;
        }
        if (mm == m)
            cout << "YES" << endl;
    }
    system("pause");
    return 0;
}
2020/9/2 10:47
加载中...