题解：P11162 [BalkanOI 2023] Car Race

首先只有相同深度的赛车可能相遇。考虑 dfs 一遍，然后在这个过程中记录每个点上一个与它深度相同的点以及它们的 LCA。LCA 可以用 tarjan 做到

O(n\alpha(n))

，也可以做到线性。

然后考虑按发生时间先后处理碰撞，相同深度的

2

点

i,j

的 LCA 的深度就是区间 min，所以可以每层一个链表维护还存在的节点，然后用优先队列维护目前最早的相遇即可，

O(n\log n)

。可以把优先队列换成桶，

O(n)

。

CPP

#include <bits/stdc++.h>
using namespace std;
int n,f[1000005],a[1000005],fd[1000005],dep[1000005],last[1000005],lst[1000005],nxt[1000005],pre[1000005];
vector<int> g[1000005],tag[1000005];
int find(int x){
	return fd[x]?fd[x]=find(fd[x]):x;
}
void dfs(int x){
	lst[x]=last[dep[x]],last[dep[x]]=x,nxt[x]=n+1;
	if(lst[x]){
		if(!a[lst[x]]) lst[x]=lst[lst[x]];
		nxt[lst[x]]=x;
		if(lst[x]){
			pre[x]=dep[find(lst[x])];
			if(a[x]) tag[pre[x]].push_back(x);
		}
	}
	for(int v:g[x])
		dfs(v);
	fd[x]=f[x];
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n,nxt[n+1]=n+1;
	for(int i=2;i<=n;i++)
		cin>>f[i],f[i]++,dep[i]=dep[f[i]]+1,g[f[i]].push_back(i);
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1);
	for(int i=1;i<=n;i++)
		if(!a[nxt[i]])
			nxt[i]=n+1;
	int mx=n;
	while(1){
		while(mx&&!tag[mx].size()) mx--;
		if(!mx) break;
		int u=tag[mx].back();
		tag[mx].pop_back();
		if(pre[u]<mx) continue;
		int l=lst[u],r=u;
		a[u]=a[l]=pre[u]=0;
		while(r<=n&&pre[nxt[r]]==mx) r=nxt[r],pre[r]=0,a[r]=0;
		while(l&&pre[l]==mx) pre[l]=0,l=lst[l],a[l]=0;
		pre[nxt[r]]=min(pre[nxt[r]],pre[l]),pre[l]=0,tag[pre[nxt[r]]].push_back(nxt[r]);
		lst[nxt[r]]=lst[l],nxt[lst[l]]=nxt[r];
	}
	for(int i=1;i<=n;i++)
		cout<<(a[i]?dep[i]:-1)<<' ';
	cout<<'\n';
	return 0;
}
/*
10
0 0 2 2 4 4 6 3 6 
0 0 1 0 0 1 1 1 1 1 
*/

题解：P11162 [BalkanOI 2023] Car Race

文章操作

相关推荐

评论

题解：P11162 [BalkanOI 2023] Car Race