淀粉质板子求调

Nemonade @ 2022-06-02 20:00:19

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define pfor(i,x,y) for(register int i=x;i<=y;++i)
#define mfor(i,x,y) for(register int i=x;i>=y;--i)
constexpr inline int maxx(const int &x,const int &y){return x>y?x:y;}
constexpr inline int minx(const int &x,const int &y){return x<y?x:y;}
constexpr inline int absx(const int &x){return (x>0)?(x):(~x+1);}
inline int read(){
    int x=0;bool flag=false;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return flag?~x+1:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=(~x+1);}
    if(x/10) write(x/10);
    putchar((x%10)^48);
    return;
}
const int N=1e4+5,M=1e2+5;
int n,m,x,y,z,mx[N],size[N],root,dist[N],q[N],tmp[N],tot;
int head[N],nxt[N<<1],ver[N<<1],edge[N<<1],tote;
vector<int> v;
bool vis[N],out[M],res[N<<12];
inline void add(int x,int y,int z){
    ver[++tote]=y,edge[tote]=z;
    nxt[tote]=head[x],head[x]=tote;
    return;
}
inline void getroot(int x,int fa,int num){
    mx[x]=0,size[x]=1;
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(y==fa||vis[y]) continue;
        getroot(y,x,num);
        size[x]+=size[y],mx[x]=maxx(mx[x],size[y]);
    }
    mx[x]=maxx(mx[x],num-size[x]);
    if(mx[x]<mx[root]) root=x;
    return;
}
inline void getsize(int x,int fa){
    v.push_back(dist[x]);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(y==fa||vis[y]) continue;
        dist[y]=dist[x]+edge[i];
        getsize(y,x);
    }
    return;
}
inline void calc(int x){
    tot=0;
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        dist[y]=edge[i];
        v.clear();
        getsize(y,-114514);
        pfor(j,0,v.size()-1) pfor(k,1,m) if(q[k]>=v[j]) out[k]|=res[q[k]-v[j]];
        pfor(j,0,v.size()-1) tmp[++tot]=v[j],res[v[j]]=true;
    }
    pfor(i,1,tot) res[tmp[i]]=false;
    return;
}
inline void solve(int x){
    vis[x]=res[0]=true;
    calc(x);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        mx[root=0]=INT_MAX;
        getroot(y,x,size[y]);
        solve(root);
    }
    return;
}
signed main(){
    n=read(),m=read();
    pfor(i,1,n-1){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    pfor(i,1,m) q[i]=read();
    mx[root=0]=INT_MAX;
    getroot(1,-114514,n);
    solve(root);
    pfor(i,1,m) puts(out[i]?"AYE":"NAY");
    return 0;
}

by Zwaire @ 2022-06-02 20:04:42

感觉您calc函数的复杂度假了吧,不应该使用双指针吗?

by LCATreap @ 2022-06-02 20:08:38

@Zwaire 这道题实测直接枚举也可以过的，看这个时间估计大概率是 getroot 写挂了之类的。

by Zwaire @ 2022-06-02 20:13:41

@wqlGZZC %%%,我以为枚举过不了的

by LCATreap @ 2022-06-02 20:17:32

看错了

by Nemonade @ 2022-06-02 20:22:33

@wqlGZZC 我康了getroot一会感觉没问题啊。。。应该是其他地方炸了。。。

by LCATreap @ 2022-06-02 20:24:03

@NemonadePanda 待我看一下

by LCATreap @ 2022-06-02 21:03:57

在 TLE 的第一个点，我把正确代码找到的 1 的重心与你的代码的重心对比，正确代码的重心是 100，你的代码的重心是 46。

by Nemonade @ 2022-06-02 21:05:41

!

by Nemonade @ 2022-06-02 21:06:11

所以getroot错了？

by LCATreap @ 2022-06-02 21:07:27

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 2e4 + 10;
const int maxk = 1e7 + 10;
const int maxm = 2e2 + 10;
int head[maxn], cnt = 0, n, m, son[maxn], siz[maxn]; ll dis[maxn], tmp[maxn];
struct edge{
    int to, next;
    ll w;
}node[maxn];
inline void add(int u, int v, ll w){
    node[cnt].next = head[u];
    node[cnt].to = v;
    node[cnt].w = w;
    head[u] = cnt++;
}
bool judge[maxk], ans[maxm], vis[maxn]; ll query[maxm];
int rt = 0, fasiz = 0, q[maxm], tot = 0;
void init(){
    memset(head, -1, maxn * sizeof(int));
}
void getrt(int u, int f = 0){
    siz[u] = 1, son[u] = 0; int v;
    for(int i = head[u]; ~i; i = node[i].next){
        v = node[i].to;
        if(v == f || vis[v])continue;
        getrt(v, u);
        siz[u] += siz[v];
        if(siz[v] > son[u])son[u] = siz[v]; 
    }
    son[u] = max(son[u], fasiz - siz[u]);
    if(son[u] < son[rt])rt = u;
}

void solve(int u, int f = 0){
    if(dis[u] >= 1e7)return;
    tmp[tot++] = dis[u]; int v;
    for(int i = head[u]; ~i; i = node[i].next){
        v = node[i].to;
        if(v == f || vis[v])continue;
        dis[v] = dis[u] + node[i].w;
        solve(v, u);
    }
}
queue<int>que;
void getans(int u){
    int v;
    for(int i = head[u]; ~i; i = node[i].next){
        v = node[i].to;
        if(vis[v])continue;
        tot = 0;
        dis[v] = node[i].w;
        solve(v, u);
        for(int j = 0; j < tot; j++){
            for(int k = 0; k < m; k++){
                if(query[k] >= tmp[j])ans[k] |= judge[query[k] - tmp[j]];
            }
        }
        for(int j = 0; j < tot; j++){
            que.push(tmp[j]);
            judge[tmp[j]] = true;
        }
    }
    while(!que.empty())judge[que.front()] = false, que.pop();
}
void divide(int u){
    vis[u] = judge[0] = true;
    getans(u); int v;
    for(int i = head[u]; ~i; i = node[i].next){
        v = node[i].to;
        if(vis[v])continue;
        son[rt = 0] = fasiz = siz[v];
        getrt(v), getrt(rt);
        divide(rt);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    cin >> n >> m;
    int u, v; ll w; init();
    for(int i = 1; i < n; i++){
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    for(int i = 0; i < m; i++)cin >> query[i];
    son[0] = fasiz = n;
    getrt(1);
    cout << rt << endl;
    exit(0);
    divide(rt);
    for(int i = 0; i < m; i++){
        if(ans[i])cout << "AYE\n";
        else cout << "NAY\n";
    }
    return 0;
}

这是输入

输出是 100。