QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#634634#5313. Please Save Pigelandfengwu2005Compile Error//C++144.5kb2024-10-12 17:47:012024-10-12 17:47:01

Judging History

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

  • [2024-10-12 17:47:01]
  • 评测
  • [2024-10-12 17:47:01]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int read()
{
    int ret=0;bool f=0;char c=getchar();
    while(c>'9'||c<'0')f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return f?-ret:ret;
}
const int maxn=5e5+5;
int n,k;
class gcd_sol
{
    ll d,x;
    bool emp;
    public:
    gcd_sol(){emp=true;}
    void add(ll v){d+=v;}
    void addv()
    {
        emp=false;
        x=gcd(x,d);
        d=0;
    }
    ll query()
    {
        return abs(gcd(d,x));
    }
    friend gcd_sol add(gcd_sol a,ll v)
    {
        a.add(v);return a;
    }
    friend gcd_sol merge(gcd_sol a, gcd_sol b)
    {
        if(b.emp)return a;
        if(a.emp)return b;
        a.x = gcd(a.x, b.x);
        a.x = gcd(a.x, b.d - a.d);
        return a; 
    }
    void print()
    {
        cout<<d<<' '<<x<<endl;
    }
};
class len_sol
{
    ll d,x;
    public:
    len_sol(){d=x=0;}
    void add(ll v){d+=v*x;}
    void addx(){x++;}
    void print()
    {
        cout<<d<<' '<<x<<endl;
    }
    ll query()
    {
        return d;
    }
    friend len_sol add(len_sol a,ll v)
    {
        a.add(v);return a;
    }

    friend len_sol merge(len_sol a, len_sol b)
    {
        a.d+=b.d;
        a.x+=b.x;
        return a; 
    }
};

class graph
{
    vector<pair<int,int>>e[maxn];
    public:
    bool c[maxn];
    void link(int x,int y,int v)
    {
        e[x].push_back({y,v});
        e[y].push_back({x,v});
    }
    ll sum[maxn],d[maxn];
    gcd_sol g[maxn];
    len_sol l[maxn];
    void dfs0(int u,int fa)
    {
        if(c[u])
        {
            g[u].addv();
            l[u].addx();
        }
        for(auto[i,v]:e[u])
        {
            if(i==fa)continue;
            dfs0(i,u);
            g[u]=merge(g[u],add(g[i],v));
            l[u]=merge(l[u],add(l[i],v));
        }
        for(int i=0;i<e[u].size();i++)
        {
            if(e[u][i].first==fa)
            {
                e[u].erase(e[u].begin()+i);
                break;
            }
        }
    }
    void dfs1(int u,int fa)
    {
        sum[u]=merge(l[u],l[fa]).query();

        d[u]=merge(g[u],g[fa]).query();
        assert(d[u]);
        

        vector<gcd_sol>pregcd(e[u].size()),sufgcd(e[u].size());
        
        vector<len_sol>prelen(e[u].size()),suflen(e[u].size());
        
        if(!e[u].empty())
        {
            pregcd[0]=add(g[e[u][0].first],e[u][0].second);
            for(int i=1;i<e[u].size();i++)
                pregcd[i]=merge(pregcd[i-1],add(g[e[u][i].first],e[u][i].second));
            sufgcd[e[u].size()-1]=add(g[e[u].back().first],e[u].back().second);
            for(int i=(int)e[u].size()-2;i>=0;i--)
                sufgcd[i]=merge(sufgcd[i+1],add(g[e[u][i].first],e[u][i].second));
            
            prelen[0]=add(l[e[u][0].first],e[u][0].second);
            for(int i=1;i<e[u].size();i++)
                prelen[i]=merge(prelen[i-1],add(l[e[u][i].first],e[u][i].second));
            suflen[e[u].size()-1]=add(l[e[u].back().first],e[u].back().second);
            for(int i=(int)e[u].size()-2;i>=0;i--)
                suflen[i]=merge(suflen[i+1],add(l[e[u][i].first],e[u][i].second));
            
        }

        for(int i=0;i<e[u].size();i++)
        {
            auto [t,v] = e[u][i];
            g[u] = merge(i?pregcd[i-1]:gcd_sol(), i+1<e[u].size()?sufgcd[i+1]:gcd_sol());
            l[u] = merge(i?prelen[i-1]:len_sol(), i+1<e[u].size()?suflen[i+1]:len_sol());

            g[u] = merge(g[u], g[fa]);
            l[u] = merge(l[u], l[fa]);

            if(c[u])
            {
                g[u].addv();
                l[u].addx();
            }

            g[u].add(v);
            l[u].add(v);

            dfs1(t,u);
        }
    }

}o;
int main()
{
    // srand(time(0));
    // n=5e5;k=1e3;
    // n=5e4;k=1e3;
    // for(int i=1;i<=k;i++)
    // {
    //     o.c[rand()%n+1]=true;
    // }
    // for(int i=2;i<=n;i++)
    // {
    //     int u=i,v=rand()%(i-1)+1,w=rand()%1000000+1;
    //     o.link(u,v,w);
    // }
    n=read();k=read();
    for(int i=1;i<=k;i++)
        o.c[read()]=true;
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        o.link(u,v,w);
    }
    if(k==1)
    {
        puts("0");
        return 0;
    }
    o.dfs0(1,0);
    o.dfs1(1,0);
    ll ans=1e18;
    for(int i=1;i<=n;i++)
    {

        ans=min(ans,o.sum[i]/o.d[i]);
    }
    printf("%lld\n",ans*2);
    return 0;
}

Details

answer.code: In member function ‘void gcd_sol::addv()’:
answer.code:23:11: error: ‘gcd’ was not declared in this scope
   23 |         x=gcd(x,d);
      |           ^~~
answer.code: In member function ‘ll gcd_sol::query()’:
answer.code:28:20: error: ‘gcd’ was not declared in this scope
   28 |         return abs(gcd(d,x));
      |                    ^~~
answer.code: In function ‘gcd_sol merge(gcd_sol, gcd_sol)’:
answer.code:38:15: error: ‘gcd’ was not declared in this scope
   38 |         a.x = gcd(a.x, b.x);
      |               ^~~
answer.code: In member function ‘void graph::dfs0(int, int)’:
answer.code:95:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   95 |         for(auto[i,v]:e[u])
      |                 ^
answer.code: In member function ‘void graph::dfs1(int, int)’:
answer.code:143:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  143 |             auto [t,v] = e[u][i];
      |                  ^