为什么
  • 板块灌水区
  • 楼主Igallta
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/12/23 10:58
  • 上次更新2023/12/23 13:31:47
查看原帖
为什么
813622
Igallta楼主2023/12/23 10:58

Windows环境下一点问题没有,洛谷在线 IDE (Linux) 就 RE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL k<<1
#define RR l<<1|1
#define lg log2
const int MAXN=901;
struct edge {
	int to,next;
} w[MAXN*2+1];
int h[MAXN+1],cnt=1,d[MAXN+1],prt[MAXN+1],p[MAXN+1][11],n,m,root=1;
set<int>st;
map<int,int>mp;
void AddEdge(int x,int y) {
	w[cnt].to=y;
	w[cnt].next=h[x];
	h[x]=cnt++;
}
void DFS(int x,int deep){
	d[x]=d[deep]+1;
	p[x][0]=deep;
	for(int i=1;(1<<i)<=d[x];i++) {
		p[x][i]=p[p[x][i-1]][i-1];
	}
	for(int i=h[x]; i; i=w[i].next){
		if(deep!= w[i].to)DFS(w[i].to,x);
	}
}
int LCA(int a,int b) {
	int k,i;
	if(d[a]<d[b])swap(a,b);
	k=lg(d[a]);
	for(i=k; i>=0; i--)if(d[a]-(1<<i)>=d[b])a=p[a][i];
	if(a==b)return b;
	for(i=k; i>=0; i--)
		if(p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int x,y,count;
	while(scanf("%lld",&n)){
		for(int i=1; i<=n; i++) {
			scanf("%lld:(%lld)",&x,&count);
			while(count--){
				scanf(" %lld",&y);
				AddEdge(x,y);
				prt[y]=x;
			} 
		}
		//寻找root 
		while(prt[root])root=prt[root];
		DFS(root,0);
		cin>>m;
		for(int i=1; i<=m; i++) {
			scanf(" (%lld,%lld)",&x,&y);
			int lca=LCA(x,y);//降低时间复杂度 
			st.insert(lca);
			++mp[lca];
		}
		for(auto kt:st){
			printf("%lld:%lld\n",kt,mp[kt]);
		}	
		mp.clear();
		st.clear();
		cnt=1;		
        root=1;
	    for(int i=0;i<=MAXN;i++){
	    	d[i]=0;
			prt[i]=0;
			h[i]=0;
			w[i].to=0;
			w[i].next=0;
			for(int j=0;j<=10;j++)p[i][j]=-1;
		}
	for(int i=MAXN+1;i<=2*MAXN;i++){
			w[i].to=0;
			w[i].next=0;
		}
	}
	return 0;
}
input:
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5)
(1,4)
(4,2)
(2,3)
(1,3)
(4,3)
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5)
(1,4)
(4,2)
(2,3)
(1,3)
(4,3)
output:
2:1
5:5
2:1
5:5
2023/12/23 10:58
加载中...