QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279330#5313. Please Save Pigelandone_god_and_two_dogs#RE 3ms18308kbC++143.1kb2023-12-08 16:11:152023-12-08 16:11:15

Judging History

你现在查看的是最新测评结果

  • [2023-12-08 16:11:15]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:18308kb
  • [2023-12-08 16:11:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ls p<<1
#define rs p<<1|1
const int M=5e5+5;
int n,k;
int c[M],Tot;
int hd[M],to[M<<1],nx[M<<1],val[M<<1];
void add(int u,int v,int w) {
    nx[++Tot]=hd[u];
    to[Tot]=v;val[Tot]=w;
    hd[u]=Tot;
}
int L[M],R[M],lt[M],tot;
void dfs(int now,int Fa) {
    L[now]=++tot;lt[tot]=now;
    for(int i=hd[now]; i; i=nx[i]) {
        int To=to[i];
        if(To==Fa)continue;
        dfs(To,now);
    }
    R[now]=tot;
}
int A[M];
bool mk[M];
LL dis[M],ans;
void redfs(int now,int Fa) {
    for(int i=hd[now]; i ;i=nx[i]) {
        int To=to[i];
        if(To==Fa)continue;
        dis[To]=dis[now]+val[i];
        redfs(To,now);
    }
}
LL gcd(LL a,LL b) {
    if(!b)return a;
    return gcd(b,a%b);
}
struct SEG {
    LL W[M<<2];
    void update(int p,int l,int r,int pos,LL D) {
        if(l==r) {
            W[p]+=D;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid)update(ls,l,mid,pos,D);
        else update(rs,mid+1,r,pos,D);
        W[p]=gcd(abs(W[ls]),abs(W[rs]));
    }
}T;
LL sum;
void ddfs(int now,int Fa,int w) {
    if(now!=1) {
        int lx=lower_bound(A+1,A+k+1,L[now])-A;
        int rx=upper_bound(A+1,A+k+1,R[now])-A-1;
        if(lx<=rx) {
            T.update(1,1,k,lx,-w);
            if(rx<k)T.update(1,1,k,rx+1,w);
        }
        if(lx>1) {
            T.update(1,1,k,1,w);
            T.update(1,1,k,lx,-w);
        }
        if(rx<k) {
            T.update(1,1,k,rx+1,w);
        }
        sum+=1LL*((k-rx+lx-1)-(rx-lx+1))*w;
        ans=min(ans,sum/T.W[1]);
        // cout<<now<<" "<<lx<<" "<<rx<<endl;
        // for(int i=1; i<=k; ++i)
        //     cout<<T.Query(1,1,k,i)<<" ";
        // cout<<endl;
        // cout<<endl;
        // if(ans==2)cout<<ans<<" "<<sum<<" "<<T.W[1]<<" "<<now<<" "<<lx<<" "<<rx<<" "<<T.Query(1,1,k,3)<<endl;
    }
    for(int i=hd[now]; i; i=nx[i]) {
        int To=to[i];
        if(To==Fa)continue;
        ddfs(To,now,val[i]);
    }
    if(now!=1) {
        int lx=lower_bound(A+1,A+k+1,L[now])-A;
        int rx=upper_bound(A+1,A+k+1,R[now])-A-1;
        if(lx<=rx) {
            T.update(1,1,k,lx,w);
            if(rx<k)T.update(1,1,k,rx+1,-w);
        }
        if(lx>1) {
            T.update(1,1,k,1,-w);
            T.update(1,1,k,lx,w);
        }
        if(rx<k) {
            T.update(1,1,k,rx+1,-w);
        }
        sum-=1LL*((k-rx+lx-1)-(rx-lx+1))*w;
    }
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1; i<=k; ++i)scanf("%d",&c[i]);
    for(int i=1; i<n; ++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    for(int i=1; i<=k; ++i)A[i]=L[c[i]],mk[c[i]]=true;
    sort(A+1,A+k+1);
    redfs(1,0);
    for(int i=1; i<=k; ++i) {
        sum+=dis[lt[A[i]]];
        T.update(1,1,k,i,dis[lt[A[i]]]-dis[lt[A[i-1]]]);
        //cout<<dis[lt[A[i]]]<<" "<<dis[lt[A[i-1]]]<<" "<<lt[A[i]]<<" "<<lt[A[i-1]]<<endl;
    }
    //cout<<T.Query(1,1,3,3)<<endl;
    ans=sum/T.W[1];
    ddfs(1,0,0);
    printf("%lld",ans*2);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 18308kb

input:

5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 18248kb

input:

10 3
1 7 10
7 6 3
1 8 3
3 6 3
8 6 2
4 1 1
10 6 4
2 8 3
9 10 3
5 10 3

output:

24

result:

ok 1 number(s): "24"

Test #3:

score: -100
Runtime Error

input:

1 1
1

output:


result: