40TLE求助!P5836
  • 板块学术版
  • 楼主__vector__
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/12/3 21:55
  • 上次更新2023/11/3 23:02:31
查看原帖
40TLE求助!P5836
507348
__vector__楼主2021/12/3 21:55

后几个测试点经测试似乎是读入上TLE了。
我的测试方法:在读入语句后面放上多余输出,原来AC的WA了,原来TLE的还是TLE,说明读入TLE了。
大佬们看一下是怎么回事,O(n)读入居然TLE:

#include <bits/stdc++.h>//希望有生之年能看到CCF用IOI赛制&CSP2022 rp++
//lca调了半天不行,算了用并查集
using namespace std;
const int maxn=	1e5+5;
int n,m;
char lx[maxn];
int f[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int find(int x)
{
	return x==f[x]?x:find(f[x]);
}

int main()
{
	for(int i=1;i<maxn;i++)f[i]=i;
	scanf("%d%d",&n,&m);
	scanf("%s",lx+1);
    int x,y;
    for(int i=1;i<n;i++)
    {
    	x=read();
    	y=read();
    	if(lx[x]==lx[y])
    	{
    		int ta=find(x);
			int tb=find(y);
			f[ta]=tb;//将相同颜色弄成连通块
		}
    }
    int ai,bi;
    char ci;
    for(int i=1;i<=m;i++)
    {
    	ai=read();
    	bi=read();
    	scanf("%c",&ci);
    	if(find(ai)==find(bi)&&lx[ai]!=ci)printf("0");//如果在同一个连通块且其中一个不符合要求,其他一定不符合要求
    	else printf("1");
    }
    
    return 0;
}
2021/12/3 21:55
加载中...