QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589016 | #5313. Please Save Pigeland | louhao088# | WA | 0ms | 14072kb | C++23 | 2.7kb | 2024-09-25 15:42:00 | 2024-09-25 15:42:00 |
Judging History
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'