QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589016#5313. Please Save Pigelandlouhao088#WA 0ms14072kbC++232.7kb2024-09-25 15:42:002024-09-25 15:42:00

Judging History

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

  • [2024-09-25 15:42:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14072kb
  • [2024-09-25 15:42:00]
  • 提交

answer

#include<bits/stdc++.h>
#define Lson (now<<1)
#define Rson (now<<1|1)
using namespace std;

typedef pair<int,int> pr;
typedef long long ll;

const int MAXN=5e5,SIZE=1048576;
const ll INF=3e18;

inline int Read(){
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}

ll GCD(ll a,ll b) {return b ? GCD(b,a%b) : a;}
inline ll ABS(ll x) {return x>0 ? x : -x;}

int n,K,C[MAXN+5],B[MAXN+5];
vector<pr> Tree[MAXN+5];
int Size[MAXN+5],DFN[MAXN+5],dnum,sum[MAXN+5];
ll dis[MAXN+5],ans=INF,A[MAXN+5];
bool V[MAXN+5];

void CalMsg(int now,int fa)
{
    Size[now]=1;
    DFN[now]=++dnum;
    for(int i=0,rear;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa) continue;
        dis[rear]=dis[now]+Tree[now][i].second;
        CalMsg(rear,now);
        Size[now]+=Size[rear];
        sum[now]+=sum[rear];
    }
}

ll g[SIZE+5];
inline void PushUp(int now) {g[now]=GCD(g[Lson],g[Rson]);}
void Build(int now,int L,int R)
{
    if(L==R) {g[now]=A[L];return;}
    int mid=(L+R)>>1;
    Build(Lson,L,mid),Build(Rson,mid+1,R);
    PushUp(now);
}
void Add(int now,int L,int R,int x,int v)
{
    if(L==R) {g[now]+=v;return;}
    int mid=(L+R)>>1;
    if(x<=mid) Add(Lson,L,mid,x,v);
    else Add(Rson,mid+1,R,x,v);
    PushUp(now);
}
inline void Modify(int L,int R,int v)
{
    if(L>R) return;
    Add(1,1,K,L,v);
    if(R<K) Add(1,1,K,R+1,-v);
}

ll S;
void Solve(int now,int fa)
{
    ans=min(ans,ABS(S/g[1]));
    for(int i=0,rear,cost;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa) continue;
        cost=Tree[now][i].second;
        S+=1ll*cost*(K-2*sum[rear]);
        int L=lower_bound(B+1,B+K+1,DFN[rear])-B;
        int R=lower_bound(B+1,B+K+1,DFN[rear]+Size[rear])-B-1;
        Modify(1,L-1,-cost),Modify(L,R,cost),Modify(R+1,K,-cost);
        Solve(rear,now);
        S-=1ll*cost*(K-2*sum[rear]);
        Modify(1,L-1,cost),Modify(L,R,-cost),Modify(R+1,K,cost);
    }
}

bool cmp(int a,int b) {return DFN[a]<DFN[b];}

int main()
{
    n=Read(),K=Read();
    for(int i=1;i<=K;i++) ++sum[C[i]=Read()],V[C[i]]=1;
    if(K==1) return printf("0\n"),0;
    for(int i=1,a,b,c;i<n;i++)
    {
        a=Read(),b=Read(),c=Read();
        Tree[a].push_back(make_pair(b,c));
        Tree[b].push_back(make_pair(a,c));
    }
    CalMsg(1,0);
    sort(C+1,C+K+1,cmp);
    for(int i=1;i<=K;i++) A[i]=dis[C[i]],B[i]=DFN[C[i]];
    for(int i=K;i;i--) A[i]-=A[i-1];
    Build(1,1,K);
    for(int i=1;i<=K;i++) S+=dis[C[i]];
    Solve(1,0);
    printf("%lld\n",2*ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14072kb

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: -100
Wrong Answer
time: 0ms
memory: 11980kb

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:

2

result:

wrong answer 1st numbers differ - expected: '24', found: '2'