Mars_Cat

    在开头位置%%%nbdhhzh。正是他的出现使窝们陷入了万劫不复的境地。

    咦？有点偏了。。。

    好像自己有思路的就只有第一题哦~于是我们先来看一看我们的第一题。

程序自动分析（内存限制：512MB  时间限制：1s  代码长度限制：1024KB）

	n范围	i,j范围	约定
1	1≤n≤1000	1≤i,j≤10000	e∈{0,1}
2
3
4	1≤n≤100000
5
6
7		1≤i,j≤100000000
8
9
10

    看到这题可以发现这题的形式很像NOI2015中的一题。然而好像如果（和NOI2015的那题）用一样的算法必死无疑。所以窝们要再想想。

    看到题目之后的第一反应应该是并查集吧。窝们看到了这个数据范围之后会觉得i,j很大（但还是没有黈力大），这个时候记录Father节点似乎本蒟蒻不怎么会。。。

    于是就可以看到n。。。(不错不错十分美味)发现n只有少少的100000也就是说不重复的数字出现的最多为200000！于是似乎可以<li>乱<san>搞<hua>一下。然后就可以用裸裸的并查集来判断元素是否相同了。至于元素不同？直接在每个并查集的最终Father节点那里记录下与它不相等的集合的最终Father子节点离散化以后的序号。。

    似乎问题就解决了。。

    然而。。判着判着似乎TLE了

3400

mars_cat

1935

时间超限36%

405216

2004

C++

4075 B

2015-08-05 16:22:34

    这是怎么回事呢？听说是合并集合的时候爆掉了。。就像这样！

 

while(!N[gfy].empty())
{
    N[gfx].insert(GF(*N[gfy].begin()));
    N[gfy].erase(N[gfy].begin());
}

    然后被黈力骂了

    啊。。于是就启发式合并了一下A掉了。。

 

3403

mars_cat

1935

正确

405480

204

C++/Edit

4131 B

2015-08-05 16:51:15

最终代码如下：（请无视那些长长的读入优化。。）

 

#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <ctime>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
 
using namespace std;
 
#define gch getchar
#define mp make_pair
 
char C_get;
void read(int &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
    }
}
 
void read(long long &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
    }
}
 
void read(double &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
        if(C_get=='.')
        {
            double n=1;
            for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())n/=10,x=x-(C_get+'0')*n;
        }
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
        if(C_get=='.')
        {
            double n=1;
            for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())n/=10,x=x+(C_get-'0')*n;
        }
    }
}
void read(char x){x=gch();}
void read(char x[]){gets(x);}
 
int MAP[100000010];
int tt=0;
 
int n,x,y,e;
set <int> N[200010];
int F[200010];
int gfx,gfy;
 
int GF(int xx)//Get_Father
{
    if(F[xx]!=xx)
    {
        F[xx]=GF(F[xx]);
    }
    return F[xx];
}
 
int main()
{
    memset(MAP,0,sizeof(MAP));
    memset(F,0,sizeof(F));
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(x); read(y); read(e);
        if(MAP[x]==0)MAP[x]=++tt,N[tt].clear();
        if(MAP[y]==0)MAP[y]=++tt,N[tt].clear();
        x=MAP[x]; y=MAP[y];
        if(!F[x])F[x]=x;
        if(!F[y])F[y]=y;
        if(e)/*x==y*/
        {
            if(x==y)
            {
                puts("YES");
                continue;
            }
            gfx=GF(x);gfy=GF(y);
            if(N[gfx].count(gfy))
            {
                puts("NO");
                continue;
            }
            if(N[gfy].count(gfx))
            {
                puts("NO");
                continue;
            }
            puts("YES");
            if(gfx==gfy)continue;
            if(N[gfy].size()>N[gfx].size())swap(gfx,gfy);
            F[gfy]=gfx;
            while(!N[gfy].empty())
            {
                N[gfx].insert(GF(*N[gfy].begin()));
                N[gfy].erase(N[gfy].begin());
            }
        }
        else/*x!=y*/
        {
            gfx=GF(x);gfy=GF(y);
            if(gfx==gfy)
            {
                puts("NO");
                continue;
            }
            puts("YES");
            N[gfx].insert(gfy);
            N[gfy].insert(gfx);
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1935
    User: mars_cat
    Language: C++
    Result: 正确
    Time:204 ms
    Memory:405480 kb
****************************************************************/

可接受。。除了内存比较蛤蛤。。