求助大佬,关于数据范围
查看原帖
求助大佬,关于数据范围
251466
wwldx楼主2020/7/16 22:37

这题极限数据范围,n是2e5,m是4e5,但是我maxn开2e5却会因为小了而TLE,test2和test10会T,但maxn开到4e5或者以上就能过,是我哪里写小了吗? 下为代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1000000007;
const int maxn=200050;
const int inf=0x3f3f3f3f;
const int INF=0x7f7f7f7f;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
#define msi(a) memset(a,inf,sizeof(a))
#define iossync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// head
int n,m;
int c[maxn];
struct node{
	int x,y;
	int x1,y1; 
}a[maxn],b[maxn<<1];
int fa[maxn]; 
void init()//初始化 
{
	rep(i,1,n+1)
	fa[i]=i,c[i]=m+1;
	
}
struct Node{
	int v,next;
}edge[maxn<<1];
int head[maxn];
int cnt;
void addedge(int u,int v)
{
	edge[++cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
int find(int x)//查找 
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int x,int y)//合并 
{
	x=find(x);
	y=find(y);
	if(x!=y)
	{
		fa[max(x,y)]=fa[min(x,y)];
	}
}

void change(int v,int t)
{
	if(c[v]==m+1)
	{
		c[v]=t;
	}
	for(int j=head[v];j;j=edge[j].next)
	{
		int d=edge[j].v;
		if(c[d]==m+1)
		change(d,t);
	}
}
int main()
{
	iossync
	cin>>n>>m;
	init();
	rep(i,1,n+1)
	{
		cin>>a[i].x>>a[i].y;
	}
	rep(i,1,m+1)
	{
		cin>>b[i].x>>b[i].y;
		if(b[i].y==1)
		{
			a[b[i].x].x1=1;
		}
		else
		a[b[i].x].y1=1;
	}
	rep(i,1,n+1)
	{
		if(a[i].x!=-1 && a[i].x1==0)
		{
			unite(i,a[i].x);
			addedge(i,a[i].x);
			addedge(a[i].x,i);
		}
		if(a[i].y!=-1 && a[i].y1==0)
		{
			unite(i,a[i].y);
			addedge(i,a[i].y);
			addedge(a[i].y,i);
		}
	}
	// 逆向建图,松手等于拉手
	rep(i,1,n+1)
	if(find(i)==1)
	{
		c[i]=-1;
	}
	per(i,1,m+1)
	{
		int asd;//连接的点 
		if(b[i].y==1)
		{
			a[b[i].x].x1=0;
			asd=a[b[i].x].x;
		}
		else
		a[b[i].x].y1=0,asd=a[b[i].x].y;
		if(asd==-1)
		continue;
		unite(asd,b[i].x);
		addedge(asd,b[i].x);
		addedge(b[i].x,asd);
		if(find(asd)==1)
		{
			if(c[asd]==m+1)
			{
				c[asd]=i-1;
			}
			for(int j=head[asd];j;j=edge[j].next)
			{
				int d=edge[j].v;
				if(c[d]==m+1)
				change(d,i-1);
			}
		}
	}
	rep(i,1,n+1)
	{
		cout<<c[i]<<"\n";
	}
	return 0;
}
2020/7/16 22:37
加载中...