QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#268502#5313. Please Save PigelandLynkcat#WA 3ms48264kbC++203.0kb2023-11-28 18:01:202023-11-28 18:01:20

Judging History

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

  • [2023-11-28 18:01:20]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:48264kb
  • [2023-11-28 18:01:20]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=500005;
struct node
{
    int mn,all,sm,tot;
    node()
    {
        mn=inf;
        all=sm=tot=0;
    }
}in[N],out[N];
int n,m;
int vis[N];
vector<pa>G[N];
node merge(node x,node y)
{
            x.sm+=y.sm;
            x.tot+=y.tot;
            int t=min(x.mn,y.mn);
            if (x.mn<inf)
                x.all=__gcd(x.all,x.mn-t);
            if (y.mn<inf)
                x.all=__gcd(x.all,y.mn-t);
            x.all=__gcd(x.all,y.all);
            x.mn=t;
    return x;
}
node add(node x,int w)
{
    x.sm+=x.tot*w;
    x.mn+=w;
    return x;
}
void dfs(int k,int fa)
{
    for (auto [u,w]:G[k])
    {
        if (u==fa) continue;
        dfs(u,k);
        in[k]=merge(in[k],add(in[u],w));
    }
    if (vis[k]) 
    {
        node nw;
        nw.mn=0;
        nw.tot=vis[k];
        in[k]=merge(in[k],nw);
    }
}
void dfs1(int k,int fa)
{
    if (vis[k])
    {
        node nw;
        nw.mn=0;
        nw.tot=vis[k];
        out[k]=merge(out[k],nw);
    }
    vector<node>pre(G[k].size());
    vector<node>suf(G[k].size());
    for (int i=0;i<G[k].size();i++)
    {
        auto [u,w]=G[k][i];
        if (u==fa) continue;
        if (i>0) pre[i]=pre[i-1];
        pre[i]=merge(pre[i],add(in[u],w));
    }
    for (int i=sz(G[k])-1;i>=0;i--)
    {
        auto [u,w]=G[k][i];
        if (u==fa) continue;
        if (i+1<sz(G[k])) suf[i]=suf[i+1];
        suf[i]=merge(suf[i],add(in[u],w));
    }
    for (int i=0;i<G[k].size();i++)
    {
        auto [u,w]=G[k][i];
        if (u==fa) continue;
        node nw=out[k];
        if (i>0) nw=merge(nw,pre[i-1]);
        if (i+1<sz(G[k])) nw=merge(nw,suf[i+1]);
        nw=add(nw,w);
        out[u]=nw;
    }
    for (auto [u,w]:G[k])
    {
        if (u==fa) continue;
        dfs1(u,k);
    }
}
void BellaKira()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        vis[x]+=1;
    }
    for (int i=1;i<n;i++) 
    {
        int x,y,w;
        cin>>x>>y>>w;
        G[x].push_back(mp(y,w));
        G[y].push_back(mp(x,w));
    }
    dfs(1,0);
    dfs1(1,0);
    int ans=inf;
    for (int i=1;i<=n;i++)
    {
        in[i]=merge(in[i],out[i]);
        // cout<<i<<" "<<in[i].all<<" "<<in[i].sm<<endl;
        if (__gcd(in[i].all,in[i].mn)==0)
            ans=0;
        else
            ans=min(ans,(in[i].sm)/__gcd(in[i].all,in[i].mn));
    }
    cout<<ans*2<<'\n';
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/ 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 48208kb

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

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:

2

result:

wrong answer 1st numbers differ - expected: '24', found: '2'