社区讨论

救救蒟蒻吧!

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mi7w3313
此快照首次捕获于
2025/11/21 04:34
4 个月前
此快照最后确认于
2025/11/21 04:34
4 个月前
查看原帖
2/8号点WA 代码又臭又长而且用到了很多没用的东西 大佬勿喷
这题快要逼我面向数据编程了!!
CPP
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define next ewqioque 
#define free hrtpewyi//防止奇怪的ce
using namespace std;

const int N=50003;
typedef long long LL;

struct Edge{int val,to,next;}edge[N<<1];
int head[N],cnt,n;
LL low,high,mid;
inline void add(int _to,int from,int _val){
    edge[++cnt].to=_to;edge[cnt].val=_val;edge[cnt].next=head[from];head[from]=cnt;
}

int fa[N][18],depth[N];
LL d[N];

inline int Read(){
    register int x=0,c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
    return x;
}

void beizeng(int now,int father,int dep,LL dist)
{
    fa[now][0]=father;
    d[now]=dist;depth[now]=dep;
    
    int tp=log2(dep);
    for(int i=1;i<=tp;i++)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    
    for(int i=head[now];i;i=edge[i].next)
        if(edge[i].to!=father) beizeng(edge[i].to,now,dep+1,dist+edge[i].val);
}
struct ooo{
    int army,subtree;
    bool operator <(const ooo &t)const{
        if(subtree!=t.subtree)return subtree<t.subtree;
        return d[army]>d[t.army];
    }
}k[N];
int m;
vector< pair<int,int> >sons;//1号节点的子节点

inline LL D(int son,int father)
{
    return d[son]-d[father];
} 

inline pair<int,LL> jump(int node,LL dist)
{
    int tp=log2(depth[node]);
    while(tp>=0&&node){
        while(node&&tp>=0&&D(node,fa[node][tp])>dist) tp--;
        while(node&&tp>=0&&D(node,fa[node][tp])<=dist) {
            dist-=D(node,fa[node][tp]);
            node=fa[node][tp];
        }
    }
    if(!node)node=1;
    return make_pair(node,dist);
}

bool vis[N];
bool check(int now,int father)
{
    if(vis[now])return true;
    
    bool isleafnode=true;
    for(int i=head[now];i;i=edge[i].next)
        if(edge[i].to!=father)
            {
                isleafnode=false;
                if(!check(edge[i].to,now))return false;
            }
            
     return !isleafnode;
}

inline void prework(){
    n=Read();
    for(int i=1;i<n;i++)
    {
        int u=Read(),v=Read(),w;high+=(w=Read());
        add(u,v,w),add(v,u,w);
    }
    beizeng(1,0,1,0);
    m=Read();
    for(int i=1;i<=m;i++)
    {
        k[i].army=Read();
        k[i].subtree=jump(k[i].army,d[k[i].army]-1).first;
    }
    sort(k+1,k+1+m);
    
    for(int i=head[1];i;i=edge[i].next)
        sons.push_back(make_pair(edge[i].val,edge[i].to));
    sort(sons.begin(),sons.end());
}

pair<int,LL>ans[N];

LL free[N];int tp;
bool ok(LL dist){
    int i,j;
    memset(vis,0,sizeof(vis));
    tp=0;
    for(i=1;i<=m;i++){
        ans[i]=jump(k[i].army,dist);
        vis[ans[i].first]=1;
    }
    for(i=1;i<=m;i++)
        if(ans[i].first==1)
        {
        	if(check(k[i].subtree,1))free[++tp]=ans[i].second;
        	vis[k[i].subtree]=1;
        }
    sort(free+1,free+1+tp);
    for(i=tp,j=sons.size()-1;i&&j>=0;i--,j--)
    {
        while(vis[sons[j].second]=check(sons[j].second,1)&&j>=0)j--;
        if(j<0)return true;
        if(free[i]<sons[j].first)return false;
    }
    
    for(;j>=0;j--)
        if(!vis[sons[j].second]&&!check(sons[j].second,1))return false;
    return true; 
} 

LL work(){
    if(sons.size()>m)return -1;
    while(low<high)
    {
        mid=(low+high)>>1;
        if(ok(mid))high=mid;
        else low=mid+1;
    }
    return low;
}
int main(){
    prework();
    printf("%lld",work());
}

回复

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

正在加载回复...