QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694359#5313. Please Save PigelandGolem__#RE 0ms24048kbC++175.4kb2024-10-31 17:46:412024-10-31 17:46:43

Judging History

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

  • [2024-10-31 17:46:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:24048kb
  • [2024-10-31 17:46:41]
  • 提交

answer

#include<random>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
// #define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
// #define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
// #define int LL
// #define double long double
#define mkp make_pair
#define par pair<int,int>
#define epb emplace_back
#define psb push_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
    // return getchar();
    static char buf[Mxxx],*p1=buf,*p2=buf;
    return (p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2))?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
    // return fl?0:putchar(ch),0;
    static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
    return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
    char ch=gc();
    int gans=0,gflag=0;
    for(;ch<'0'||'9'<ch;ch=gc())gflag|=(ch=='-');
    for(;'0'<=ch&&ch<='9';ch=gc())gans=(gans<<1)+(gans<<3)+(ch^48);
    return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
    char ch=gc();
    int gflag=0;gans=0;
    for(;ch<'0'||'9'<ch;ch=gc())gflag|=(ch=='-');
    for(;'0'<=ch&&ch<='9';ch=gc())gans=(gans<<1)+(gans<<3)+(ch^48);
    return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
    if(x>9)write(x/10);
    pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
    if(x<0)x=-x,pc('-');
    write(x),pc(ch);
}
inline void writechar(char x,char ch)
{
    pc(x),pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
    return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
    return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
    return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
    x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
    x=Min(x,y);
}
const int Mx=5e5;
int n,K,cnt,h[Mx+5],nxt[(Mx<<1)+5],tto[(Mx<<1)+5],val[(Mx<<1)+5];
inline void ade(int x,int y,int v)
{
    nxt[++cnt]=h[x];
    tto[h[x]=cnt]=y;
    val[cnt]=v;
}
inline void Ade(int x,int y,int v)
{
    ade(x,y,v);ade(y,x,v);
}
int c[Mx+5],flg[Mx+5];
int tot[Mx+5];LL sml[Mx+5];
inline void DFS1(int x,int y)
{
    int i,to;
    tot[x]=flg[x];
    for(i=h[x];i;i=nxt[i])if((to=tto[i])^y)
    {
        DFS1(to,x);
        tot[x]+=tot[to];
        sml[x]+=sml[to];
        sml[x]+=(LL)tot[to]*val[i];
    }
}
LL sum[Mx+5];
inline void DFS2(int x,int y,LL s,int t)
{
    int i,to,tt;
    sum[x]=s+sml[x];
    // cout<<"Ck_sumx:"<<x<<":"<<sum[x]<<"||"<<s<<" "<<t<<"\n";
    for(i=h[x];i;i=nxt[i])if((to=tto[i])^y)
    {
        tt=t+tot[x]-tot[to];
        DFS2(to,x,s+sml[x]-sml[to]-(LL)tot[to]*val[i]+(LL)tt*val[i],tt);
    }
}
inline LL Gcd(LL x,LL y)
{
    return !y?x:Gcd(y,x%y);
}
inline void Mrg(LL&x,LL&y,LL v,LL w)
{
    y=Gcd(Gcd(y,w),Abs(x-v));
}
int fff[Mx+5];LL len[Mx+5],dlt[Mx+5];
int lsf[Mx+5];LL lsl[Mx+5],lsd[Mx+5];
inline void DFS3(int x,int y)
{
    int i,to;
    fff[x]=flg[x];
    for(i=h[x];i;i=nxt[i])if((to=tto[i])^y)
    {
        DFS3(to,x);
        lsf[to]=fff[x];
        lsl[to]=len[x];
        lsd[to]=dlt[x];
        if(fff[x]&&fff[to])Mrg(len[x],dlt[x],len[to]+val[i],dlt[to]);
        else if(fff[to])len[x]=len[to]+val[i],dlt[x]=dlt[to];
        fff[x]|=fff[to];
    }
}
LL ans;
inline void DFS4(int x,int y,LL l,LL d,int f)
{
    int i;int ff;LL ll,dd;vector<par>tmp;tmp.clear();
    ll=l;dd=d;
    if(f&&fff[x])Mrg(ll,dd,len[x],dlt[x]);
    else if(fff[x])ll=len[x],dd=dlt[x];
    // if(x==1)cout<<"Ck_assert:"<<x<<" "<<((f|fff[x])!=0)<<":"<<(!(sum[x]%Gcd(ll,dd)))<<"\n";
    // if(x==1)cout<<"Ck_val:"<<sum[x]/Gcd(ll,dd)<<"||"<<sum[x]<<" "<<ll<<" "<<dd<<"\n";
    // cout<<"Ck_assert:"<<x<<" "<<((f|fff[x])!=0)<<":"<<(!(sum[x]%Gcd(ll,dd)))<<"||"<<f<<" "<<fff[x]<<"\n";
    // cout<<"Ck_val:"<<sum[x]/Gcd(ll,dd)<<"||"<<sum[x]<<" "<<ll<<" "<<dd<<"?|?"<<l<<" "<<d<<" "<<f<<"\n";
    // cout<<"\n";
    // assert(ff=f|fff[x]);
    // assert(!(sum[x]%Gcd(ll,dd)));
    ckmn(ans,sum[x]/Gcd(ll,dd));
    for(i=h[x];i;i=nxt[i])if(tto[i]^y)tmp.epb(mkp(tto[i],val[i]));
    reverse(tmp.begin(),tmp.end());
    int to,vl;
    for(par pr:tmp)
    {
        to=f(pr);vl=s(pr);
        ff=f|lsf[to];
        ll=(f?l:(lsf[to]?lsl[to]:0))+(ff?vl:0);
        dd=Gcd(Gcd(d,lsd[to]),f&&lsf[to]?Abs(lsl[to]-l):0);
        // cout<<"edge:"<<x<<"->"<<to<<":"<<ll<<" "<<dd<<" "<<ff<<"||"<<l<<" "<<d<<" "<<f<<"?"<<lsl[to]<<" "<<lsd[to]<<" "<<lsf[to]<<"\n";
        DFS4(to,x,ll,dd,ff);
        if(f&&fff[to])Mrg(l,d,len[to]+vl,dlt[to]);
        else if(fff[to])l=len[to]+vl,d=dlt[to];
        f|=fff[to];
    }
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("_.in","r",stdin);
    // freopen("_.out","w",stdout);
    #endif
    int i,x,y;n=read();K=read();
    for(i=1;i<=K;i++)flg[c[i]=read()]=1;
    for(i=1;i<n;i++)x=read(),y=read(),Ade(x,y,read());
    ans=LLONG_MAX;DFS1(1,0);DFS2(1,0,0,0);
    DFS3(1,0);DFS4(1,0,0,0,0);
    writenum(ans<<1,10);
    return output;
}
/*
 5 3
 3 4 5
 1 2 2
 2 3 4
 2 5 4
 3 4 6
*/

详细

Test #1:

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

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: 22216kb

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: