提高二 疫情控制 70pts WA on #4#8#9 求助

常规
1

原题

提交记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll h[50005],e[100005],ne[100005],le[100005],idx;
ll b[50005],a[50005],lt[50005],fi[50005];
ll f[50005][18],dis[50005][18],vis[50005],depth[50005];
ll sd[50005],need[50005];
ll armies[50005],cnt;
ll at[50005],cnt1,bt[50005],cnt2;
bool cmp(ll a,ll b){
    return lt[a]<lt[b];
}
void add(ll a,ll b,ll c){
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    le[idx]=c;
}
void dfs(ll now,ll fa,ll d){
    vis[now]=1;
    f[now][0]=fa,dis[now][0]=d;
    depth[now]=depth[fa]+1;
    for (ll i=1;i<=17;i++){
        f[now][i]=f[f[now][i-1]][i-1];
        dis[now][i]=dis[now][i-1]+dis[f[now][i-1]][i-1];
    }
    for (ll i=h[now];i;i=ne[i]){
        ll j=e[i];
        if (j==fa)continue;
        if (!vis[j]){
            dfs(j,now,le[i]);
        }
    }
}
bool find(ll now,ll fa){
    if (sd[now])return 1;
    bool leaf=1;
    for (ll i=h[now];i;i=ne[i]){
        ll j=e[i];
        if (j==fa)continue;
        leaf=0;
        if (!find(j,now))return 0;
    }
    if (leaf)return 0;
    else return 1;
}
bool check(ll t){
    memset(lt,0,sizeof(lt));
    for (int i=1;i<=m;i++)a[i]=b[i];
    cnt=cnt1=cnt2=0;
    for (ll i=1;i<=m;i++){
        lt[i]=t;
        //cout<<i<<" "<<a[i]<<" "<<lt[i]<<endl;
        for (ll j=17;j>=0;j--){
            if (f[a[i]][j]>1&&lt[i]>=dis[a[i]][j]){
                //cout<<i<<" "<<j<<" "<<a[i]<<" "<<lt[i]<<endl;
                lt[i]-=dis[a[i]][j];
                a[i]=f[a[i]][j];
            }
        }
        if (f[a[i]][0]==1&&lt[i]>=dis[a[i]][0]){
            armies[++cnt]=i;
        }
        else fi[i]=1,sd[a[i]]=1;
        //cout<<i<<" "<<a[i]<<" "<<lt[i]<<endl;
    }
    for (ll i=h[1];i;i=ne[i]){
        ll j=e[i];
        if (!find(j,1)){
            need[j]=1;
            //cout<<j<<endl;
        }
    }
    sort(armies+1,armies+cnt+1,cmp);
    for(ll i=1;i<=cnt;i++){
        if (need[a[armies[i]]]&&lt[armies[i]]<2*dis[a[armies[i]]][0]){
            need[a[armies[i]]]=0;
        }
        else {
            at[++cnt1]=lt[armies[i]]-dis[a[armies[i]]][0];
            //cout<<"t1 "<<cnt1<<" "<<i<<" "<<at[cnt1]<<endl;
        }
    }
    for (ll i=h[1];i;i=ne[i]){
        ll j=e[i];
        if (need[j]){
            bt[++cnt2]=dis[j][0];
            //cout<<"t2 "<<cnt2<<" "<<j<<" "<<bt[cnt2]<<endl;
        }
    }
    if (cnt1<cnt2)return 0;
    sort(at+1,at+cnt1+1);
    sort(bt+1,bt+cnt2+1);
    int i=1,j=1;
    for(;i<=cnt1&&j<=cnt2;){
        if (at[i]>=bt[j]){
            i++,j++;
        }
        else i++;
    }
    if (j>cnt2)return 1;
    else return 0;
}
int main(){
    cin>>n;
    for (ll i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    depth[0]=-1;
    dfs(1,0,0);
    cin>>m;
    for (ll i=1;i<=m;i++)cin>>b[i];
    ll l=0,r=1e15,mid,hs=0;
    while (l<r){
        //cout<<l<<" "<<r<<endl;
        mid=(l+r)/2;
        if (check(mid)){
            r=mid;
            hs=1;
        }
        else l=mid+1;
    }
    if (hs)cout<<r<<endl;
    else cout<<-1<<endl;
    return 0;
}
2 个赞
2

已A，没清空数组，此贴结

3 个赞