Submission #975426

#	Time	Username	Problem	Language	Result	Execution time	Memory
975426		Tuanlinh123	Road Closures (APIO21_roads)	C++17	100 / 100	294 ms	79260 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
const ll maxn=100005, inf=1e17;
 
struct SegTree
{
    ll n;
    vector <ll> val, cnt, sum;
 
    void init(vector <ll> &v)
    {
        val=v, n=sz(val);
        cnt.assign(n*4+1, 0), sum.assign(n*4+1, 0);
    }
 
    void update(ll i, ll Start, ll End, ll idx, ll v)
    {
        if (Start==End) return cnt[i]+=v, sum[i]+=val[idx]*v, void();
        ll mid=(Start+End)/2;
        if (mid>=idx) update(i*2, Start, mid, idx, v);
        else update(i*2+1, mid+1, End, idx, v);
        cnt[i]=cnt[i*2]+cnt[i*2+1], sum[i]=sum[i*2]+sum[i*2+1];
    }
    void add(ll x) {update(1, 0, n-1, lower_bound(val.begin(), val.end(), x)-val.begin(), 1);}
    void sub(ll x) {update(1, 0, n-1, lower_bound(val.begin(), val.end(), x)-val.begin(), -1);}
 
    ll Sum(ll i, ll Start, ll End, ll k)
    {
        if (Start==End)
        {
            if (cnt[i]<k) return inf;
            return val[Start]*k;
        }
        ll mid=(Start+End)/2;
        if (cnt[i*2]>=k) return Sum(i*2, Start, mid, k);
        return min(inf, sum[i*2]+Sum(i*2+1, mid+1, End, k-cnt[i*2]));
    }
    ll Sum(ll k) {return Sum(1, 0, n-1, k);}
 
    ll Find(ll i, ll Start, ll End, ll k)
    {
        if (Start==End)
        {
            if (cnt[i]<k) return inf;
            return val[Start];
        }
        ll mid=(Start+End)/2;
        if (cnt[i*2]>=k) return Find(i*2, Start, mid, k);
        return Find(i*2+1, mid+1, End, k-cnt[i*2]);
    }
    ll Find(ll k) {return Find(1, 0, n-1, k);}
};
 
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) 
{
    vector <vector <pll>> A(n), At(n);
    for (ll i=0; i<sz(W); i++)
        A[U[i]].pb({V[i], W[i]}), A[V[i]].pb({U[i], W[i]});
    vector <SegTree> S(n);
    vector <vector <ll>> H(n);
    for (ll i=0; i<n; i++)
    {
        vector <ll> num;
        for (auto [v, w]:A[i]) num.pb(w);
        sort(num.begin(), num.end());
        num.resize(unique(num.begin(), num.end())-num.begin());
        H[sz(A[i])-1].pb(i), S[i].init(num);
        for (auto [v, w]:A[i]) S[i].add(w);
    }
    vector <ll> cr, check(n, 0), answer(n, 0);
    vector <array<ll, 2>> dp(n);
    for (ll i=n-1; i>=0; i--)
    {
        for (ll u:H[i])
        {
            for (auto [v, w]:A[u])
                At[v].pb({u, w}), S[v].sub(w);
            cr.pb(u);
        }
        function <void(ll, ll, ll )> dfs=[&](ll u, ll wpa, ll pa)
        {
            check[u]=1, dp[u][0]=0, dp[u][1]=wpa;
            for (ll j=0; j<2; j++)
            {
                vector <ll> num;
                ll cnt=sz(A[u])-i-j;
                for (auto [v, w]:At[u])
                {
                    if (v==pa) continue;
                    if (!check[v]) dfs(v, w, u);
                    dp[u][j]+=dp[v][0];
                    if (dp[v][1]<dp[v][0]) dp[u][j]+=dp[v][1]-dp[v][0], cnt--;
                    else num.pb(dp[v][1]-dp[v][0]);
                }
                if (cnt<=0) continue;
                dp[u][j]+=S[u].Sum(cnt);
                sort(num.begin(), num.end());
                for (ll i=0; i<sz(num) && cnt; i++)
                {
                    if (num[i]<S[u].Find(cnt)) dp[u][j]+=num[i]+S[u].Sum(cnt-1)-S[u].Sum(cnt), cnt--;
                    else break;
                }
            }
        };
        for (ll u:cr)
            if (!check[u])
                dfs(u, 0, u), answer[i]+=dp[u][0];
        for (ll u:cr) check[u]=0;
    }
    return answer;
} 

• 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