QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#219528#5313. Please Save PigelandisaunoyaRE 0ms24172kbC++233.9kb2023-10-19 15:59:502023-10-19 15:59:51

Judging History

你现在查看的是最新测评结果

  • [2023-10-19 15:59:51]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:24172kb
  • [2023-10-19 15:59:50]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
const int N=500005;
const long long INF=1e18;
int n,k;
int c[N];
int dfnc[N];
vector<pair<int,int>>G[N];
int dfn[N],ed[N],Index;
long long dis[N],b[N];
void init(int u,int father)
{
  dfn[u]=++Index;
  for(auto [v,w]:G[u])
  {
    if(v==father) continue;
    dis[v]=dis[u]+w;
    init(v,u);
  }
  ed[u]=Index;
  return;
}
struct Segment_Tree
{
  #define ls i*2
  #define rs i*2+1
  struct Node
  {
    int l,r;
    long long g,sum,tag;
  }tree[N*4];
  Node merge(const Node &a,const Node &b)
  {
    Node c;
    c.l=a.l,c.r=b.r;
    c.tag=0;
    c.sum=a.sum+b.sum;
    c.g=gcd(a.g,b.g);
    return c;
  }
  void push_up(int i)
  {
    tree[i]=merge(tree[ls],tree[rs]);
    return;
  }
  void add(int i,long long v)
  {
    tree[i].sum+=(tree[i].r-tree[i].l+1)*v;
    tree[i].tag+=v;
    return;
  }
  void push_down(int i)
  {
    if(!tree[i].tag) return;
    add(ls,tree[i].tag);
    add(rs,tree[i].tag);
    tree[i].tag=0;
    return;
  }
  void build(int i,int l,int r)
  {
    tree[i].l=l,tree[i].r=r;
    tree[i].tag=0;
    if(l==r)
    {
      tree[i].sum=dis[c[l]];
      tree[i].g=b[l];
      return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(i);
    return;
  }
  void modify(int i,int u,long long v)
  {
    if(tree[i].l==tree[i].r)
    {
      tree[i].g+=v;
      return;
    }
    push_down(i);
    if(u<=tree[ls].r) modify(ls,u,v);
    else modify(rs,u,v);
    push_up(i);
    return;
  }
  void add(int i,int l,int r,long long v)
  {
    if(l<=tree[i].l&&tree[i].r<=r) return add(i,v);
    push_down(i);
    if(l<=tree[ls].r) add(ls,l,r,v);
    if(r>=tree[rs].l) add(rs,l,r,v);
    push_up(i);
    return;
  }
  Node query(int i,int l,int r)
  {
    if(l<=tree[i].l&&tree[i].r<=r) return tree[i];
    push_down(i);
    if(r<=tree[ls].r) return query(ls,l,r);
    else if(l>=tree[rs].l) return query(rs,l,r);
    else return merge(query(ls,l,r),query(rs,l,r));
  }
  void print(int i)
  {
    if(tree[i].l==tree[i].r)
    {
      cerr<<tree[i].g<<" ";
      return;
    }
    push_down(i);
    print(ls);
    print(rs);
    return;
  }
  #undef ls
  #undef rs
}T;
long long ans=INF;
void dfs(int u,int father)
{
  auto res=T.query(1,1,k);
  if(res.g<0) res.g=-res.g;
  ans=min(ans,res.sum*2/res.g);
//  cerr<<"now"<<u<<" "<<res.sum<<" "<<res.g<<" res: "<<res.sum*2/res.g<<"\n";
//  T.print(1);
//  cerr<<"\n";
  for(auto [v,w]:G[u])
  {
    if(v==father) continue;
    int l=lower_bound(dfnc+1,dfnc+k+1,dfn[v])-dfnc;
    int r=upper_bound(dfnc+1,dfnc+k+1,ed[v])-dfnc-1;
//    cerr<<"find"<<l<<" "<<r<<"\n";
    if(l<=r)
    {
//      cerr<<"add"<<l<<" "<<r<<"\n";
      T.modify(1,l,-w);
      if(r+1<=k) T.modify(1,r+1,w);
      T.add(1,l,r,-w);
    }
    if(1<=l-1)
    {
//      cerr<<"add"<<1<<" "<<l-1<<"\n";
      T.modify(1,1,w);
      if(l<=k) T.modify(1,l,-w);
      T.add(1,1,l-1,w);
    }
    if(r+1<=k)
    {
//      cerr<<"add"<<r+1<<" "<<k<<"\n";
      T.modify(1,r+1,w);
      T.add(1,r+1,k,w);
    }
    dfs(v,u);
    if(l<=r)
    {
      T.modify(1,l,w);
      if(r+1<=k) T.modify(1,r+1,-w);
      T.add(1,l,r,w);
    }
    if(1<=l-1)
    {
      T.modify(1,1,-w);
      if(l<=k) T.modify(1,l,w);
      T.add(1,1,l-1,-w);
    }
    if(r+1<=k)
    {
      T.modify(1,r+1,-w);
      T.add(1,r+1,k,-w);
    }
  }
  return;
}
int main()
{
  cin>>n>>k;
  for(int i=1;i<=k;i++)
    cin>>c[i];
  for(int i=1;i<n;i++)
  {
    int x,y,z;
    cin>>x>>y>>z;
    G[x].emplace_back(y,z);
    G[y].emplace_back(x,z);
  }
  init(1,0);
  sort(c+1,c+k+1,[=](const int &x,const int &y){return dfn[x]<dfn[y];});
  for(int i=1;i<=k;i++)
    dfnc[i]=dfn[c[i]];
  for(int i=1;i<=k;i++)
    b[i]=dis[c[i]]-dis[c[i-1]];
  T.build(1,1,k);
  dfs(1,0);
  cout<<ans;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22000kb

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: 0ms
memory: 24172kb

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

output:


result: