Submission #1209992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209992		12345678	Road Closures (APIO21_roads)	C++20	24 / 100	2130 ms	1114112 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

mt19937 rng(12345678);

ll n, dp[nx][2], sm[nx], tot;
vector<pair<ll, ll>> d[nx];

struct treap
{
    struct node
    {
        ll sm, vl, key, sz;
        node *l, *r;
        node(ll vl): sm(vl), vl(vl), key(rng()), sz(1), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt;
    ll getsz(pnode x) {return x?x->sz:0;}
    ll getsm(pnode x) {return x?x->sm:0;}
    void update(pnode x)
    {
        if (!x) return;
        x->sz=1+getsz(x->l)+getsz(x->r);
        x->sm=x->vl+getsm(x->l)+getsm(x->r);
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l||!r) return k=l?l:r, void();
        if (l->key>=r->key) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
    }
    void split(pnode &l, pnode &r, pnode k, int key)
    {
        if (!k) return l=r=0, void();
        if (1+getsz(k->r)<=key) split(l, k->l, k->l, key-(1+getsz(k->r))), r=k;
        else split(k->r, r, k->r, key), l=k;
        update(l), update(r);
    }
    void splitlowerbound(pnode &l, pnode &r, pnode k, ll vl)
    {
        if (!k) return l=r=0, void();
        if (k->vl>=vl) splitlowerbound(l, k->l, k->l, vl), r=k;
        else splitlowerbound(k->r, r, k->r, vl), l=k;
        update(l), update(r);
    }
    void insert(ll vl)
    {
        pnode p1, p2, p3=new node(vl);
        splitlowerbound(p1, p2, rt, vl);
        merge(p1, p3, rt);
        merge(rt, p2, rt);
    }
    ll query(ll k)
    {
        pnode p1, p2;
        split(p1, p2, rt, k);
        auto tmp=getsm(p2);
        merge(p1, p2, rt);
        return tmp;
    }
    void show(pnode x)
    {
        if (!x) return;
        show(x->l);
        cout<<x->vl<<' ';
        show(x->r);
    }
} t[nx];

void dfs(int u, int p, ll pw, int k)
{
    //cout<<"dfs "<<u<<' '<<p<<' '<<pw<<' '<<k<<'\n';
    sm[u]=0;
    t[u].rt=0;
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w, k), sm[u]+=dp[v][0], t[u].insert(dp[v][1]-dp[v][0]);
    dp[u][0]=sm[u]+t[u].query(k);
    dp[u][1]=sm[u]+t[u].query(k-1)+pw;
    dp[u][1]=max(dp[u][1], dp[u][0]);
    //if (k==2) cout<<"dp "<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
    //if (k==2&&u==0) cout<<"treap : ", t[u].show(t[u].rt), cout<<'\n';
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n=N;
    vector<ll> mx(n);
    for (int i=0; i<n-1; i++) d[U[i]].push_back({V[i], W[i]}), d[V[i]].push_back({U[i], W[i]}), tot+=W[i];
    // minimum closure costs = total - maximum selected road
    for (int i=1; i<n; i++) dfs(0, 0, 0, i), mx[i]=dp[0][0];
    for (int i=0; i<n; i++) mx[i]=tot-mx[i];
    return mx;
}

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