40分WA求助
查看原帖
40分WA求助
239458
cmach_socket楼主2021/8/13 18:25

只过了2345测试点,其他全WA了,请帮忙看一下ToT

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define MAXN 65550
#define MAXLOG 21
using namespace std;
vector<int>g[MAXN];
vector<int>tree[MAXN];
vector<int>ug[MAXN];
queue<int>q;
int n,tmpb,in[MAXN],now,d[MAXN]{1},xu[MAXN],xuk=-1,f[MAXN][MAXLOG],size[MAXN];
inline static void link(int x,int y){
	g[x].push_back(y);
	ug[y].push_back(x);
	in[y]++;
}
inline static void addson(int x,int fa){
	
		tree[fa].push_back(x);
		f[x][0]=fa;
		d[x]=d[fa]+1;
		
		for(int k=1;k<MAXLOG;k++){
			f[x][k]=f[f[x][k-1]][k-1];
		}
		
		
}
inline static void tuopu(){
	for(int i=1;i<=n;i++){
		if(!in[i]){
			link(0,i);
		}
	}
	q.push(0);
	while(!q.empty()){
		now=q.front();
		q.pop();
		xu[++xuk]=now;
		for(vector<int>::iterator it=g[now].begin();it<g[now].end();it++){
			if(!(--in[*it])){
				q.push(*it);
			}
		}
	}
}
inline static int get_lca(int x,int y){
	
	if(x==-1)return y;
	
	if(d[x]<d[y])swap(x,y);
	for(int i=MAXLOG;i>=0;i--){
		if(d[f[x][i]]>=d[y])x=f[x][i];
		
	}    
	                             
	if(x==y)return x;
	
	for(int i=MAXLOG-1;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i],y=f[y][i];
		}
	}
	 
	return f[x][0];  
}
inline static void build_tree(){
	for(int i=1;i<=xuk;i++){
		int lca=-1;
		for(vector<int>::iterator it=ug[xu[i]].begin();it<ug[xu[i]].end();it++){
			
			lca=get_lca(lca,*it);
		}
		addson(xu[i],lca);
	}
}
inline static void dfs(int x){
	size[x]=1;
	for(vector<int>::iterator it=tree[x].begin();it<tree[x].end();it++){
		dfs(*it);
		size[x]+=size[*it];
	}
}

int main(){
	freopen("P2597_1.in","r",stdin);
	freopen("P2597_1.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&tmpb);
			if(tmpb){
				link(tmpb,i);
			}
			else break;
		}
	}
	tuopu();
	build_tree();
	dfs(0);
	for(int i=1;i<=n;i++){
		printf("%d\n",size[i]-1);
	}
	return 0;
} 
2021/8/13 18:25
加载中...