QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279329 | #5313. Please Save Pigeland | one_god_and_two_dogs# | RE | 3ms | 20100kb | C++14 | 3.1kb | 2023-12-08 16:10:31 | 2023-12-08 16:10:31 |
Judging History
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];
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18252kb
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: 3ms
memory: 20100kb
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