Submission #1061852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061852		alexdd	Road Closures (APIO21_roads)	C++17	0 / 100	103 ms	41232 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
vector<long long> rez;
set<pair<int,int>> con_heavy[100005],con_light[100005];
vector<int> ofsiz[100005];
bool isheavy[100005];
bool visited[100005];
long long dp[100005][2];
int degree[100005],parent[100005];
long long getlight(int nod, int cnt)
{
    if(cnt<=0)
        return 0;
    auto it = con_light[nod].begin();
    long long sum=0;
    while(cnt>0 && it!=con_light[nod].end())
    {
        if((*it).second!=parent[nod])
        {
            sum += (*it).first;
            cnt--;
        }
        it++;
    }
    if(cnt>0)
        return INF;
    return sum;
}
void dfs(int nod, long long up, int k)
{
    visited[nod]=1;
    vector<pair<long long,int>> v;
    long long sum=0;
    for(auto [w,x]:con_heavy[nod])
    {
        if(visited[x])
            continue;
        parent[x]=nod;
        dfs(x,w,k);
        v.push_back({dp[x][1]-dp[x][0],x});
        sum += dp[x][0];
    }
    sort(v.begin(),v.end());
    vector<int> usor;
    if(up==INF)///nu are parinte
    {
        dp[nod][1]=dp[nod][0]=INF;
        for(int i=0;i<=(int)v.size();i++)
        {
            dp[nod][0] = min(dp[nod][0], sum + getlight(nod,(degree[nod]-k)-i));

            if(i<(int)v.size()) sum += v[i].first;
        }
    }
    else
    {
        dp[nod][1]=dp[nod][0]=INF;
        for(int i=0;i<=(int)v.size();i++)
        {
            dp[nod][0] = min(dp[nod][0], sum + getlight(nod,(degree[nod]-k)-i));
            dp[nod][1] = min(dp[nod][1], sum + up + getlight(nod,(degree[nod]-k)-i-1));

            if(i<(int)v.size()) sum += v[i].first;
        }
    }
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    rez.resize(N);
    for(int i=0;i<N-1;i++)
    {
        con_light[U[i]].insert({W[i],V[i]});
        con_light[V[i]].insert({W[i],U[i]});
    }
    for(int i=0;i<N;i++)
    {
        degree[i] = con_light[i].size();
        ofsiz[degree[i]].push_back(i);
    }
    vector<int> heavy_nodes;
    for(int k=N-1;k>=0;k--)
    {
        for(int x:ofsiz[k+1])
        {
            isheavy[x]=1;
            heavy_nodes.push_back(x);
            set<pair<int,int>> news;
            for(auto [w,y]:con_light[x])
            {
                if(isheavy[y])
                {
                    con_light[y].erase({w,x});
                    con_heavy[x].insert({w,y});
                    con_heavy[y].insert({w,x});
                }
                else
                    news.insert({w,y});
            }
            con_light[x] = news;
        }
        for(auto x:heavy_nodes)
            visited[x]=0;
        rez[k]=0;
        for(auto x:heavy_nodes)
        {
            if(!visited[x])
            {
                dfs(x,INF,k);
                rez[k] += dp[x][0];
            }
        }
    }
    return rez;
}

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