震惊!点分治不吸氧直接取第一个点竟过luogu模版!

P3806 【模板】点分治 1

cdbbla @ 2019-08-21 21:01:26

记录在此,铁证如山

附上代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+1e3;
const int M=110;
const int K=1e7+1e3;
const int inf=233333333+K;

inline int read()
{
    int s=0;
    char c=getchar(),lc='+';
    while (c<'0'||c>'9') lc=c,c=getchar();
    while (c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return lc=='-'?-s:s;
}
int n,m,head[N],cnt=0;
struct edge
{
    int to,val,next;
}e[2*N];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
bool ans[M],vis[N],can[K];
int q[N],len[N],query[M];
void getlength(int now,int father,int dis)
{
    len[++len[0]]=dis;
    for (int i=head[now];i;i=e[i].next)
    if (e[i].to!=father&&!vis[e[i].to]) getlength(e[i].to,now,dis+e[i].val);
}
void doing(int now)
{
    int tail=0;
    for (int i=head[now];i;i=e[i].next)
    {
        len[0]=0;
        int to=e[i].to;
        getlength(to,now,e[i].val);

        for (int j=1;j<=m;j++)
        if (!ans[j])
        for (int k=1;k<=len[0];k++)
        if (query[j]>=len[k]) ans[j]|=can[query[j]-len[k]];

        for (int j=1;j<=len[0];j++)
        if (!can[len[j]])
        {
            q[++tail]=len[j];
            can[len[j]]=1;
        }
    }
    for (int i=1;i<=tail;i++) can[q[i]]=0;
}
void dfz(int now)
{
    vis[now]=can[0]=1;
    doing(now);
    for (int i=head[now];i;i=e[i].next)
    if (!vis[e[i].to])
    {
        int to=e[i].to;
        dfz(to);
    }
}

int main()
{
    memset(vis,0,sizeof(vis));
    memset(can,0,sizeof(can));
    memset(ans,0,sizeof(ans));
    memset(head,0,sizeof(head));
    n=read();
    m=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }
    for (int i=1;i<=m;i++) query[i]=read();
    for (int i=1;i<=m;i++) if (!query[i]) ans[i]=1;
    dfz(1);
    for (int i=1;i<=m;i++)
    if (ans[i]) puts("AYE");
           else puts("NAY");

    return 0;
}

数据过水,建议加强


by cdbbla @ 2019-08-21 21:01:48

不过貌似已经有人提出了,,


by Hjcc @ 2019-08-21 21:02:42

@管理员


by Seauy @ 2019-08-21 21:09:11


|