关于此题时限
查看原帖
关于此题时限
132976
huayucaiji楼主2020/8/27 23:33

为什么在BZOJ上可以通过在洛谷上是TLE?有人解释一下吗?代码:

//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int maxn=1e5+10; 

int n,h[maxn],cnt,*f[maxn],*g[maxn],maxdep[maxn],sz[maxn],son[maxn],ans;
int needed_space[maxn<<2],*id=needed_space;

struct egde {
	int v,next;
}e[maxn<<1];

void addedge(int u,int v) {
	e[++cnt].v=v;
	e[cnt].next=h[u];
	h[u]=cnt;
}
void insert(int u,int v) {
	addedge(u,v);
	addedge(v,u);
}

int dfs1(int u,int fa) {
	int mx=0;
	for(int i=h[u];i;i=e[i].next) {
		int v=e[i].v;
		
		if(v!=fa) {
			dfs1(v,u);
			
			if(maxdep[v]>mx) {
				mx=maxdep[v];
				son[u]=v;
			}
		}
	}
	maxdep[u]=maxdep[son[u]]+1;
}

int dfs(int u,int fa) {
	if(son[u]) {
		f[son[u]]=f[u]+1;
		g[son[u]]=g[u]-1;
		dfs(son[u],u);
	}
	f[u][0]=1;
	ans+=g[u][0];
	
	for(int i=h[u];i;i=e[i].next) {
		int v=e[i].v;
		
		if(v!=son[u]&&v!=fa) {
			f[v]=id;
			id+=maxdep[v]<<1;
			g[v]=id;
			id+=maxdep[v]<<1;
			
			dfs(v,u);
			
			for(int j=0;j<maxdep[v];j++) {
				if(j>0) {
					ans+=f[u][j-1]*g[v][j];
				}
				ans+=g[u][j+1]*f[v][j];
			}
			for(int j=0;j<maxdep[v];j++) {
				g[u][j+1]+=f[u][j+1]*f[v][j];
				if(j>0) {
					g[u][j-1]+=g[v][j];
				}
				f[u][j+1]+=f[v][j];
			}
		}
	}
}

signed main() {
	n=read();
	for(int i=1;i<n;i++) {
		insert(read(),read());
	}
	
	dfs1(1,0);
	f[1]=id;
	id+=maxdep[1]<<1;
	g[1]=id;
	id+=maxdep[1]<<1;
	
	dfs(1,0);
	
	cout<<ans<<endl;
	return 0;
}

2020/8/27 23:33
加载中...