70分？？？

Wiaorziy @ 2017-11-09 14:13:45

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
long long fa[111010];
long long m,num[111010],x[111010],y[111010],xi[111010],yi[111010]; 
char character[110010];
int find(int p)
{
    return p==fa[p]?p:fa[p]=find(fa[p]);
}
void unio(int tx,int ty)
{
    int fx=find(tx),fy=find(ty);
    fa[fx]=fy;
}
int n;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>num[i]>>x[i]>>y[i];
            xi[i]=find(x[i]);
            yi[i]=find(y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(num[i]==1)
        {
            unio(xi[i],yi[i]);
        }
        if(num[i]==2)
            if(find(x[i])==find(y[i]))
            printf("Y\n");
            else
            printf("N\n");
    }
}

by Wiaorziy @ 2017-11-09 14:14:20

为啥70啊？？？剩下三个RE……

by Glis @ 2017-11-09 14:39:16

m<=2e5 把数组开大点就可以了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
long long fa[111010];
long long m,num[211010],x[211010],y[211010],xi[211010],yi[211010]; 
char character[110010];
int find(int p)
{
    return p==fa[p]?p:fa[p]=find(fa[p]);
}
void unio(int tx,int ty)
{
    int fx=find(tx),fy=find(ty);
    fa[fx]=fy;
}
int n;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>num[i]>>x[i]>>y[i];
            xi[i]=find(x[i]);
            yi[i]=find(y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(num[i]==1)
        {
            unio(xi[i],yi[i]);
        }
        if(num[i]==2)
            if(find(x[i])==find(y[i]))
            printf("Y\n");
            else
            printf("N\n");
    }
}

by fy0123 @ 2017-11-09 14:46:31

emmmm其实并不用离线的