40pts 只过了subtask 3

P3806 【模板】点分治 1

rfsfreffr @ 2022-08-16 11:49:48

很帅的代码:

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5;
const int M=1e7+5;

struct oi{
    int to;
    int w;
    int id;
};

int n,m;
int k[N];
int ans[N];
int vis[N];
vector<oi> b[N];
int minn;
int new_rt;
int len;
bool is[M];
int maxk;
int siz[N];
int sz;

void read() {
    cin>>n>>m;
    for(int i=1; i<n; i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        b[u].push_back({v,w,i});
        b[v].push_back({u,w,i});
    }
    for(int i=1; i<=m; i++) 
        scanf("%d",&k[i]),maxk=max(maxk,k[i]);
}

void dfs(int u,int fa) {
    siz[u]=1;
    int maxn=0;
    for(int i=0; i<b[u].size(); i++) {
        int v=b[u][i].to;
        int id=b[u][i].id;
        if(v==fa||vis[id]) continue;

        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxn) maxn=siz[v];
    }
    maxn=max(maxn,sz-siz[u]);
    if(maxn<minn) {
        minn=maxn;
        new_rt=u;
    }
}

void get_size(int root) {
    dfs(root,0);
    sz=siz[root];
} 

int find_core(int rt) {
    minn=2e9;
    new_rt=0;
    dfs(rt,0);
    return new_rt;
}

void check(int x) {
    for(int i=1; i<=m; i++) {
        int t=k[i]-x;
        if(t>=0&&is[t]) ans[i]=1; 
    }
}

void dfs2(int u,int fa,int len) {
    if(len>maxk) return ;
    check(len);
    for(int i=0; i<b[u].size(); i++) {
        int v=b[u][i].to;
        int w=b[u][i].w;
        int id=b[u][i].id;
        if(v==fa||vis[id]) continue;
        dfs2(v,u,len+w);
    } 
}

void add(int u,int fa,int k,int len) {
    if(len>maxk) return ;
    if(k==1) is[len]|=1;
    if(k==-1) is[len]=0; 
    for(int i=0; i<b[u].size(); i++) {
        int v=b[u][i].to;
        int w=b[u][i].w;
        int id=b[u][i].id;
        if(v==fa||vis[id]) continue;
        add(v,u,k,len+w);
    }
}

void calc(int rt,int k) {
    if(k==1) is[0]=1;
    if(k==-1) is[0]=0;
    for(int i=0; i<b[rt].size(); i++) {
        int v=b[rt][i].to;
        int w=b[rt][i].w;
        int id=b[rt][i].id;
        if(vis[id]) continue;

        if(k==1) dfs2(v,rt,w);// 和之前的桶匹配
        add(v,rt,k,w);// 放入桶中
    }
}

void solve(int u) {
    get_size(u);
    int t=find_core(u);
    int nxt=0;
    calc(t,1);

    for(int i=0; i<b[t].size(); i++) {
        int v=b[t][i].to;
        int id=b[t][i].id;
        if(vis[id]) continue;

        vis[id]=1;
        solve(v);   
        vis[id]=0;
    }

    get_size(t);
    calc(t,-1);
}

void print() {
    for(int i=1; i<=m; i++) {
        if(ans[i]==0) puts("NAY");
        if(ans[i]==1) puts("AYE");
    } 
}

int main() {
    read();
    solve(1);
    print();
    return 0;
}
/*
5 3
1 2 2
1 3 3
3 4 1
3 5 4
11 12 13
*/

by rfsfreffr @ 2022-08-16 12:21:27

发现哪里挂了,此贴完结


by Tricy @ 2023-10-26 11:21:04

也是40pts,求助楼主到底哪里写挂了?


|