首页 > 代码库 > BZOJ4122 : [Baltic2015]File paths
BZOJ4122 : [Baltic2015]File paths
对于在$o$点的某个询问，有两种情况：
情况1：走到任意一个点$x$然后超链接跳到$o$的某个祖先$y$再走到$o$。
枚举所有$y$看看是否存在$x$即可。
时间复杂度$O(nm)$。
情况2：走到$o$的某个祖先$x$，然后走到$x$子树内某个点$y$，在$x$和$y$之间不断通过超链接来回走，最后再从$x$走到$o$。
枚举$x$和$y$维护出每种环长是否可能存在，然后枚举约数判断是否存在对应的$x$和$y$即可。
时间复杂度$O(n^2+md(k))$。
#include<cstdio>#define N 3010int n,m,K,S,i,x,a[N],len[N],g[N],G[N],v[N<<1],nxt[N<<1],ed;int q[N],t,st[N],en[N],dfn,seq[N],f[2000010];bool ans[N];inline void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;}void dfs1(int x){ q[++t]=a[x]; seq[st[x]=++dfn]=a[x]; for(int i=G[x];i;i=nxt[i]){ int o=v[i]; for(int j=1;j<=t;j++){ int k=K-S-a[x]-len[o]+q[j]; if(k>=0&&k<=K)if(f[k]){ans[o]=1;break;} } } for(int i=g[x];i;i=nxt[i])dfs1(v[i]); t--; en[x]=dfn;}void dfs2(int x){ for(int i=st[x];i<=en[x];i++)f[seq[i]-a[x]+S]++; for(int i=G[x];i;i=nxt[i]){ int o=v[i]; if(ans[o])continue; int k=K-a[x]-len[o]; for(int j=1;j*j<=k;j++)if(k%j==0)if(f[j]||f[k/j]){ans[o]=1;break;} } for(int i=g[x];i;i=nxt[i])dfs2(v[i]); for(int i=st[x];i<=en[x];i++)f[seq[i]-a[x]+S]--;}int main(){ scanf("%d%d%d%d",&n,&m,&K,&S);S++; for(i=1;i<=n;i++){ scanf("%d%d",&x,&a[i]); a[i]+=a[x]+1; add(g[x],i); } for(i=1;i<=m;i++){ scanf("%d%d",&x,&len[i]); len[i]++; ans[i]=a[x]+len[i]==K; if(!ans[i])add(G[x],i); } for(i=0;i<=n;i++)f[a[i]]=1; dfs1(0); for(i=0;i<=n;i++)f[a[i]]=0; dfs2(0); for(i=1;i<=m;i++)puts(ans[i]?"YES":"NO"); return 0;}
BZOJ4122 : [Baltic2015]File paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。