QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588819#5313. Please Save Pigelandlouhao088#WA 2ms9996kbC++232.6kb2024-09-25 14:44:462024-09-25 14:44:48

Judging History

This is the latest submission verdict.

  • [2024-09-25 14:44:48]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 9996kb
  • [2024-09-25 14:44:46]
  • Submitted

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;
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,n,L,v);
    if(R<n) Add(1,1,n,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]);
        Modify(1,DFN[rear]-1,-cost);
        Modify(DFN[rear],DFN[rear]+Size[rear]-1,cost);
        Modify(DFN[rear]+Size[rear],n,-cost);
        Solve(rear,now);
        S-=1ll*cost*(K-2*sum[rear]);
        Modify(1,DFN[rear]-1,cost);
        Modify(DFN[rear],DFN[rear]+Size[rear]-1,-cost);
        Modify(DFN[rear]+Size[rear],n,cost);
    }
}

int main()
{
    n=Read(),K=Read();
    for(int i=1,C;i<=K;i++) ++sum[C=Read()],V[C]=1;
    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);
    for(int i=1;i<=n;i++) if(V[i]) A[DFN[i]]=dis[i];
    for(int i=n;i;i--) A[i]-=A[i-1];
    Build(1,1,n);
    for(int i=1;i<=n;i++) S+=dis[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: 2ms
memory: 9996kb

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: 2ms
memory: 9996kb

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:

118

result:

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