求助cf D
  • 板块学术版
  • 楼主11d10xy
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/1/10 21:45
  • 上次更新2023/10/24 04:49:27
查看原帖
求助cf D
674171
11d10xy楼主2023/1/10 21:45
#include<bits/stdc++.h>
using namespace std;
int n,a[400010],s,t;
int cnt[400010],vis[400010],pre[400010];
vector<int>lhz[400010],ids[400010];
void print(int x,int f){
	if(!x){printf("%d\n",f-1);return;}
	print(pre[x],f+1);
	printf("%d ",x);
}
int main(){
	scanf("%d",&n);
	for(int i=2;i<=300000;i++)
	if(lhz[i].empty())
	for(int j=i;j<=300000;j+=i)lhz[j].push_back(i);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for(int p:lhz[a[i]])ids[p].push_back(i);
	}
	scanf("%d%d",&s,&t);
	queue<pair<int,int> >q;
	vis[s]=1;q.push({s,a[s]});
	while(!q.empty()){
		int x=q.front().second,id=q.front().first;
		if(id==t){print(t,1);return 0;}
		q.pop();
		for(int p:lhz[x])
		if(!cnt[p]){cnt[p]=1;for(int i:ids[p])if(!vis[i]){pre[i]=id;q.push({i,a[i]});vis[i]=1;}}
	}
	printf("-1");
	return 0;
}

WA on test9

2023/1/10 21:45
加载中...