这题极限数据范围,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;
}