Submission #1061927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061927		alexdd	Road Closures (APIO21_roads)	C++17	100 / 100	237 ms	83532 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e14;

struct SegTree
{
    vector<pair<int,long long>> aint;///{cnt,sum}
    pair<int,long long> combine(pair<int,long long> x, pair<int,long long> y)
    {
        return {x.first+y.first,x.second+y.second};
    }
    void upd(int nod, int st, int dr, int poz, int newv)
    {
        if(st==dr)
        {
            if(newv>0) aint[nod] = {1,newv};
            else aint[nod] = {0,0};
            return;
        }
        int mij=(st+dr)/2;
        if(poz<=mij) upd(nod*2,st,mij,poz,newv);
        else upd(nod*2+1,mij+1,dr,poz,newv);
        aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
    }
    long long qry(int nod, int st, int dr, int k)
    {
        if(st==dr)
            return aint[nod].second;
        int mij=(st+dr)/2;
        if(aint[nod*2].first >= k)
            return qry(nod*2,st,mij,k);
        else
            return aint[nod*2].second + qry(nod*2+1,mij+1,dr,k-aint[nod*2].first);
    }
};
SegTree seg[100005];
int cate[100005];
vector<long long> rez;
set<pair<long long,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];
map<int,int> nrm[100005];
long long getlight(int nod, int cnt)
{
    if(cnt<=0)
        return 0;
    if(cnt > (int)con_light[nod].size())
        return INF;
    return seg[nod].qry(1,1,cate[nod],cnt);
}
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;
        dfs(x,w,k);
        v.push_back({dp[x][1]-dp[x][0],x});
        sum += dp[x][0];
    }
    sort(v.begin(),v.end());
    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(up!=INF) 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++)
    {
        isheavy[i]=0;
        degree[i] = con_light[i].size();
        ofsiz[degree[i]].push_back(i);
        seg[i].aint.resize(4*degree[i]+2,{0,0});
        cate[i]=0;
        for(auto it:con_light[i])
        {
            nrm[i][it.second]=++cate[i];
        }
        for(auto it:con_light[i])
        {
            seg[i].upd(1,1,cate[i],nrm[i][it.second],it.first);
        }
    }
    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<long long,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});
                    seg[x].upd(1,1,cate[x],nrm[x][y],-1);
                    seg[y].upd(1,1,cate[y],nrm[y][x],-1);
                }
                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];
            }
        }
    }
    rez[0]=0;
    for(int i=0;i<N-1;i++)
        rez[0] += W[i];
    return rez;
}

• 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