Submission #734361

#	Time	Username	Problem	Language	Result	Execution time	Memory
734361		bin9638	Road Closures (APIO21_roads)	C++17	100 / 100	621 ms	41640 KiB

roads

#include <bits/stdc++.h>

#ifndef SKY
#include "roads.h"
#endif // SKY

using namespace std;

#define N 100010
#define ll long long
#define fs first
#define sc second
#define ii pair<ll,int>
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("unroll-loops")

const ll MAX_VAL=2e14;

int cnt,k,n,ktr[N],spec[N];
vector<ii>g[N],edge[N];
ll tong,them,cost[N],dp[N][2];
vector<ll>sum[N];
vector<int>lis,ds[N];

struct nho
{
    void build(int u,int p)
    {
        for(auto v:g[u])
            if(v.sc!=p)
            {
                build(v.sc,u);
                cost[v.sc]=v.fs;
            }
    }

    ll solve(int u,int p,int sl,const vector<ll>&s)
    {

        if(sl<0)
            return MAX_VAL;
        ll res=0;
        for(auto v:g[u])
            if(v.sc!=p)
                if(dp[v.sc][0]<=dp[v.sc][1])
                {
                    res+=dp[v.sc][0];
                }else
                {
                    res+=dp[v.sc][1];
                }
        for(int i=0;i<(int)s.size()-sl;i++)
            res+=s[i];
        return res;
    }

    void DFS(int u,int p)
    {
        for(auto v:g[u])
            if(v.sc!=p)
                DFS(v.sc,u);
        vector<ll>s;
        for(auto v:g[u])
            if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1])
                s.pb(dp[v.sc][0]-dp[v.sc][1]);
        sort(s.begin(),s.end());
        //0
        dp[u][0]=solve(u,p,k,s)+cost[u];
        //1
        dp[u][1]=solve(u,p,k-(u!=0),s);
    }
}nho;

ll get(int u,int sl)
{
    if(sl>=sum[u].size())
        return 0;
    if(sl==0)
        return sum[u].back();
    return sum[u].back()-sum[u][sl-1];
}

ll solve(int u,int p,int sl,const vector<ll>&s)
{
    if(sl<0)
        return MAX_VAL;
    ll cong=0,res=MAX_VAL;
    for(auto v:edge[u])
        if(v.sc!=p)
        {
             if(dp[v.sc][0]<=dp[v.sc][1])
                {
                    cong+=dp[v.sc][0];
                }else
                {
                    cong+=dp[v.sc][1];
                }
        }
    if((int)s.size()<=sl)
        res=min(res,cong+get(u,sl-(int)s.size()));
    for(int i=0;i<s.size();i++)
    {
        cong+=s[i];
        if((int)s.size()-i-1<=sl)
            res=min(res,cong+get(u,sl-((int)s.size()-i-1)));
    }
    return res;
}

void DFS(int u,int p)
{
    ktr[u]=k;
    for(auto v:edge[u])
        if(v.sc!=p)
        {
            cost[v.sc]=v.fs;
            DFS(v.sc,u);
        }
    vector<ll>s;
    for(auto v:edge[u])
        if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1])
            s.pb(dp[v.sc][0]-dp[v.sc][1]);
     if((int)s.size()+(int)sum[u].size()>k-(p!=-1))
        sort(s.begin(),s.end());
    //0
    dp[u][0]=solve(u,p,k,s)+cost[u];
    //1
    dp[u][1]=solve(u,p,k-(p!=-1),s);
}

vector<long long> minimum_closure_costs(int NNN, vector<int> UUU, vector<int> VVV, vector<int> WWW)
{
    n=NNN;
    for(int i=0;i<n-1;i++)
    {
        int u=UUU[i],v=VVV[i],w=WWW[i];
        g[u].pb({w,v});
        g[v].pb({w,u});
    }
    cost[0]=1e18;
    nho.build(0,-1);
    vector<ll>kq;
    for(k=0;k<=0;k++)
    {
        nho.DFS(0,-1);
        kq.pb(dp[0][1]);
    }
    for(int i=0;i<n;i++)
        ds[(int)g[i].size()].pb(i);
    for(int i=0;i<n;i++)
        spec[i]=1;
    vector<int>luu;
    for(k=1;k<n;k++)
    {
        for(auto u:ds[k])
            luu.pb(u);
        if(k==1||luu.size()>=100)
        {
            for(auto u:luu)
                spec[u]=0;
            luu.clear();
            for(int i=0;i<n;i++)
                sum[i].clear(),edge[i].clear();
            them=tong=0;
             for(int i=0;i<n-1;i++)
                {
                    int u=UUU[i],v=VVV[i],w=WWW[i];
                    tong+=1ll*w;
                    if((int)g[u].size()<(int)g[v].size())
                        swap(u,v);
                    if(spec[u]&&spec[v])
                    {
                        edge[u].pb({w,v});
                        edge[v].pb({w,u});
                        continue;
                    }
                    if(spec[u])
                    {
                        sum[u].pb(w);
                        continue;
                    }
                    them+=1ll*w;
                }
             for(int i=0;i<n;i++)
            {
                sort(sum[i].begin(),sum[i].end(),greater<ll>());
                for(int j=1;j<sum[i].size();j++)
                    sum[i][j]+=sum[i][j-1];
            }
            lis.clear();
            for(int i=0;i<n;i++)
                if(spec[i]==1)
                    lis.pb(i);
             memset(cost,0x3f3f,sizeof(cost));
        }
         ll res=0;
        for(auto u:lis)
            if(ktr[u]!=k)
                DFS(u,-1),res+=dp[u][1];
        kq.pb(res);
    }
    return kq;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<int>U(n-1),V(n-1),W(n-1);
    for(int i=0;i<n-1;i++)
        cin>>U[i]>>V[i]>>W[i];
    vector<ll>kq=minimum_closure_costs(n,U,V,W);
    for(auto u:kq)cout<<u<<" ";
    return 0;
}
#endif

Compilation message (stderr)

roads.cpp: In member function 'long long int nho::solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:48:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   48 |             if(v.sc!=p)
      |               ^
roads.cpp: In function 'long long int get(int, int)':
roads.cpp:80:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     if(sl>=sum[u].size())
      |        ~~^~~~~~~~~~~~~~~
roads.cpp: In function 'long long int solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:191:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |                 for(int j=1;j<sum[i].size();j++)
      |                             ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22