QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107162 | #5313. Please Save Pigeland | why | RE | 2ms | 7612kb | C++14 | 2.7kb | 2023-05-20 14:57:58 | 2023-05-20 14:58:09 |
Judging History
answer
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5e5+86;
int n,k;
ll ans=0x7f7f7f7f7f7f7f7f;
struct edge{int to,nxt,w;}e[N<<1];
int head[N],tot;
void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
ll a[N],sum;
struct Segment_Tree
{
int l,r;
ll g;
}t[N<<2];
void push_up(int o){t[o].g=__gcd(t[o<<1].g,t[o<<1|1].g);}
void build(int o,int l,int r)
{
t[o].l=l,t[o].r=r;
if(l==r){t[o].g=a[l]-a[l-1];return;}
int mid=l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
push_up(o);
}
void update(int o,int x,ll k)
{
if(t[o].l==t[o].r){t[o].g+=k;return;}
if(x<=t[o<<1].r) update(o<<1,x,k);
else update(o<<1|1,x,k);
push_up(o);
}
struct node
{
int in,out;
bool f;
}p[N];
int cnt;
int dfs1(int u,int fa,ll dep)
{
p[u].in=cnt+1;
if(p[u].f) a[++cnt]=dep,p[u].out=cnt,sum+=dep;
// printf("%d %lld\n",u,dep);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].w;
if(v==fa) continue;
p[u].out=max(p[u].out,dfs1(v,u,dep+w));
}
// printf("%d %d %d\n",u,p[u].in,p[u].out);
return p[u].out;
}
void dfs2(int u,int fa)
{
ans=min(ans,sum*2/abs(t[1].g));//printf("%lld %lld\n",sum,abs(t[1].g));
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
ll w=e[i].w;
if(v==fa) continue;
sum+=-(p[v].in<=p[v].out)*(p[v].out-p[v].in+1)*w+(k-(p[v].in<=p[v].out)*(p[v].out-p[v].in+1))*w;
if(p[v].in<=p[v].out)
{
update(1,1,w);
update(1,p[v].in,-2*w);
if(p[v].out<k) update(1,p[v].out+1,2*w);
}
dfs2(v,u);
sum+=(p[v].in<=p[v].out)*(p[v].out-p[v].in+1)*w-(k-(p[v].in<=p[v].out)*(p[v].out-p[v].in+1))*w;
if(p[v].in<=p[v].out)
{
update(1,1,-w);
update(1,p[v].in,2*w);
if(p[v].out<k) update(1,p[v].out+1,-2*w);
}
}
}
template<typename T>
inline void read(T &x)
{
T k=1;char ch=getchar();x=0;
while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=k;
}
signed main()
{
read(n),read(k);
for(int i=1,x;i<=k;i++)
{
read(x);
p[x].f=true;
}
if(n==1)
{
puts("0");
return 0;
}
for(int i=1,u,v,w;i<=n-1;i++)
read(u),read(v),read(w),add(u,v,w),add(v,u,w);
dfs1(1,0,0);
build(1,1,k);
dfs2(1,0);
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7608kb
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: 2ms
memory: 7612kb
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: 0
Accepted
time: 1ms
memory: 1756kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Runtime Error
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...