1024programmer Java D.GoodSequences

D.GoodSequences

http://codeforces.com/contest/265/problem/D

Good question

First follow the method of finding prime numbers and then use the given The two nearest numbers in the array with the same prime divisor are used to build edges and then perform topology

Code and comments:

#include
#include
#include
#include
#include

#include
#include
#include
#include

#include
#include
#include
#define LL long long
# define sint short int
//#pragma comment(linker, “/STACK:1024000000,1024000000”)
using namespace std;
const int N=100005;
const int INF=0x3f3f3f3f;
//typedef pairpoint;
int head[N],I;
struct node
{
int j,next;
}side[N*100 ];
bool prime[N],a[N];
int dist[N],t[N];
queueqt;
void add(int i,int j )
{
side[I].j=j;
side[I].next=head[i];
head[i]=I++;
}
void build()
{
memset(prime,true,sizeof(prime));
for(int i=2;i<N;++i)
{
if(prime [i])
{
int pr=-1;
if(a[i])
pr=i;
for(int j=i*2;j<N; j=j+i)
{
prime[j]=false;
if(a[j])
{
if(pr==-1)
{pr =j;continue;}
add(pr,j);
//pr and j are given numbers. If they have the same divisor i, they are adjacent so build an edge
++t[ j];//Topology tag
pr=j;
}
}
}
}
}
int topology()
{
for( int i=0;i<N;++i)
if(a[i]&&t[i]==0)
{qt.push(i);dist[i]=1;}
int ans=1;
while(!qt.empty())
{
int x=qt.front();qt.pop();
for(int w=head [x];w!=-1;w=side[w].next)
{
int j=side[w].j;
–t[j];
if (t[j]==0)
{
dist[j]=dist[x]+1;//The last updated path must be the longest path
ans=dist[j]; //Update answer
qt.push(j);
}
}
}
return ans;
}
int main()
{
//freopen(“data.in”,”r”,stdin);
int n;
while(scanf(“%d”,&n)!=EOF)
{
memset( a,false,sizeof(a));
for(int i=0;i<n;++i)
{
int k;
scanf(“%d”,&k) ;
a[k]=true;
}
memset(head,-1,sizeof(head));
I=0;
memset(t,0,sizeof(t ));
build();
memset(dist,0,sizeof(dist));
printf(“%d\n”,topology());
}
return 0;
}

D. Good Sequences

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/746483

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: [email protected]

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索