社区讨论

大数据读入会有问题?

P3258[JLOI2014] 松鼠的新家参与者 5已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mi85uxxs
此快照首次捕获于
2025/11/21 09:07
4 个月前
此快照最后确认于
2025/11/21 09:07
4 个月前
查看原帖
T了两个点,数据下出来后发现大数据没法读入,求解
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int a,b,n,cnt=0,ans[1000000]={0},head[1000000]={0},jl[1000000]={0},p[1000000]={0};
int mark[1000000]={0},grand[300010][30]={0},deep[1000000]={0};
struct node{
	int to,next;
}tu[2000010];
void dfs(int x){
	for(int i=1;(1<<i)<=deep[x];i++)
		grand[x][i]=grand[ grand[x][i-1] ][ i-1 ];
	for(int i=head[x];i;i=tu[i].next){
		if(tu[i].to==grand[x][0])	continue;
		p[x]=1;
		grand[tu[i].to][0]=x;
		deep[tu[i].to]=deep[x]+1;
		dfs(tu[i].to);
	}
}
int lca(int x,int y){
	if(deep[x]>deep[y])	swap(x,y);
	int h=deep[y]-deep[x];
	for(register int i=0;(1<<i)<=h;++i){
		if(h&(1<<i))
			y=grand[y][i];
	}
	if(x==y)	return x;
	for(register int i=log2(n);i>=0;--i){
		if(grand[x][i]!=grand[y][i]){
			x=grand[x][i];
			y=grand[y][i];
		}
	}
	return grand[x][0];
}
void up(int x,int flag){
	flag+=mark[x];
	mark[x]=0;
	ans[x]+=flag;
	if(grand[x][0])
		up(grand[x][0],flag);
}
inline void add(int u,int v){
	++cnt;
	tu[cnt].to=v;
	tu[cnt].next=head[u];
	head[u]=cnt;
}
int main(){
	cin>>n;
	for(register int i=1;i<=n;++i)
		cin>>jl[i];
	for(register int i=1;i<n;++i){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	deep[1]=0;
	dfs(1);
	for(register int i=1;i<n;++i){
		++mark[jl[i]];
		++mark[jl[i+1]];
		int t=lca(jl[i],jl[i+1]);
		--mark[t];
		--mark[grand[t][0]];
		--ans[jl[i]];
	}
	for(register int i=1;i<=n;++i){
		if(!p[i])
			up(i,0);
	}
	++ans[jl[1]],--ans[jl[n]];
	for(register int i=1;i<=n;++i)
		cout<<ans[i]<<endl;
	return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...