社区讨论

为什么ce

P1084[NOIP 2012 提高组] 疫情控制参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6hjhpn
此快照首次捕获于
2025/11/20 04:59
4 个月前
此快照最后确认于
2025/11/20 04:59
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
typedef long long ll;
const int maxn=100007;
using namespace std;
ll i,j,k,l,t,n,m,ans,r,mid,yi,er;
ll a[maxn];
ll first[maxn*2],next[maxn*2],last[maxn*2],chang[maxn*2],num;
ll b[maxn],tot,f[maxn][18],g[maxn][18],deep[maxn];
ll c[maxn],d[maxn],e[maxn],wwa,vv;
bool bz[maxn],az[maxn];
struct node{
    ll w,v;
}w[maxn];
struct nod{
    ll a,b;
}v[maxn];
void add(ll x,ll y,ll z){
    last[++num]=y;
    next[num]=first[x];
    first[x]=num;
    chang[num]=z;
}
void dfs(ll x,ll y){
    int i,j,k;
    for(i=first[x];i;i=next[i]){
        if(last[i]!=y){
            f[last[i]][0]=x;
            g[last[i]][0]=chang[i];
            dfs(last[i],x);
        }
    }
}
void suan(ll x,ll y){
    int i,j,k=0;
    if(k+g[x][0]<=y&&f[x][0]){
        x=f[x][0];
        k+=g[x][0];
    }
    yi=x;er=k;
}
bool cmp(nod x,nod y){
    return x.a<y.a;
}
bool cmp1(node x,node y){
    return x.w<y.w;
}
void dfs1(ll x){
    bool dz=1,ez=1;
    for(int i=first[x];i;i=next[i]){
        if(last[i]!=f[x][0]){
            dfs1(last[i]);
            dz=0;
            if(bz[last[i]]==0)ez=0;
        }  
    }
    if(ez&&x!=1&&dz==0)bz[x]=1;
}
bool pan(ll x){
    ll i,j,p,q,o;
    wwa=vv=0;
    memset(bz,0,sizeof(bz));
    fo(i,1,m){
        o=0;
        q=a[i];p=0;
        fod(j,17,0){
            if(p+g[q][j]<=x&&f[q][j]){
                p+=g[q][j];
                q=f[q][j];
            }
        }
        if(q!=1){
            bz[q]=1;
        }
        else{
            w[++wwa].w=x-p;
            q=a[i];
            fod(j,17,0)if(f[q][j]>1)q=f[q][j];
            w[wwa].v=q;
        }
    }
    dfs1(1);
    sort(w+1,w+1+wwa,cmp1);
    for(i=first[1];i;i=next[i]){
        if(!bz[last[i]]){
            v[++vv].a=chang[i];  
            v[vv].b=last[i];
        }
    }
    sort(v+1,v+1+vv,cmp);
    if(wwa<vv)return 0;
    v[vv+1].a=0x7fffffff;
    k=1;
    fo(i,1,wwa){
        if(!bz[w[i].v])bz[w[i].v]=1;
        else if(w[i].w>=v[k].a){
            bz[v[k].b]=1;
            k++;
        }
        while(bz[v[k].b])k++;
    }
    if(k>vv)return 1;
    else return 0;
}
int main(){
    scanf("%lld",&n);
    fo(i,1,n-1){
        scanf("%lld%lld%lld",&k,&l,&t);
        add(k,l,t);
        add(l,k,t);
    }
    dfs(1,0);
    fo(j,1,17){
        fo(i,1,n){
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[f[i][j-1]][j-1]+g[i][j-1];
        }
    }
    scanf("%lld",&m);
    fo(i,1,m){
        scanf("%lld",&a[i]);
    }
    l=0;r=1000000000;
    while(l<r){
        mid=(l+r)/2;
        if(pan(mid))r=mid;else l=mid+1;
    }
    printf("%lld\n",l);
}

回复

3 条回复,欢迎继续交流。

正在加载回复...