社区讨论
救救蒟蒻吧!
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 条回复,欢迎继续交流。
正在加载回复...