QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#588819 | #5313. Please Save Pigeland | louhao088# | WA | 2ms | 9996kb | C++23 | 2.6kb | 2024-09-25 14:44:46 | 2024-09-25 14:44:48 |
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;
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'