Submission #1035561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035561		mispertion	Road Closures (APIO21_roads)	C++17	36 / 100	2033 ms	62804 KiB

roads

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

using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;

ll dp[N][2], sm[N], used[N];
int n, k, tresh = 150;
vector<pair<ll, ll>> g[N];
vector<pair<ll, ll>> ng[N];
vector<ll> vs[N];

void dfs(int v, int p, int w){
    dp[v][0] = dp[v][1] = 0;
    for(auto u : g[v])
        if(u.F != p)
            dfs(u.F, v, u.S);
    vector<pair<ll, pll>> vs = {};
    for(auto u : g[v]){
        if(u.F != p){
            vs.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}});
        }
    }
    sort(all(vs));
    reverse(all(vs));
    for(int i = 0; i < min(k, sz(vs)); i++){
        if(vs[i].F > 0){
            dp[v][0] += vs[i].S.F;
        }else{
            dp[v][0] += vs[i].S.S;
        }
    }
    for(int i = min(k, sz(vs)); i < sz(vs); i++){
        dp[v][0] += vs[i].S.S;
    }

    for(int i = 0; i < min(k - 1, sz(vs)); i++){
        if(vs[i].F > 0){
            dp[v][1] += vs[i].S.F;
        }else{
            dp[v][1] += vs[i].S.S;
        }
    }
    for(int i = min(k - 1, sz(vs)); i < sz(vs); i++){
        dp[v][1] += vs[i].S.S;
    }
    dp[v][1] += w;
}

void dfs1(int v, int p, int w){
    used[v] = 1;
    dp[v][0] = dp[v][1] = 0;
    for(auto u : ng[v]){
        if(u.F != p)
            dfs1(u.F, v, u.S);
    }
    //cout << v << '\n';
    while(sz(vs[v]) > k){
        sm[v] -= vs[v].back();
        vs[v].pop_back();
    }
    int ps = min(sz(vs[v]), k) - 1, cur = min(sz(vs[v]), k);
    vector<pair<ll, pll>> ha = {};
    for(auto u : ng[v]){
        if(u.F != p){
            ha.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}});
        }
    }
    /*cout << sm[v] << ": ";
    for(auto e : vs[v]){
        cout << e << ' ';
    }
    cout << '\n';*/
    sort(all(ha));
    reverse(all(ha));
    dp[v][0] = sm[v];
    for(auto e : ha){
        //cout << e.F << ' ' << e.S.F << ' ' << e.S.S << ' ' << ps << ' ' << cur << '\n';
        if(e.F <= 0 || ps < 0){
            dp[v][0] += e.S.S;
            //cout << "1\n";
        }else{
            if(cur < k){
                cur++;
                dp[v][0] += e.S.F;
                //cout << "2\n";
            }else{
                if(e.F > vs[v][ps]){
                    dp[v][0] -= vs[v][ps];
                    dp[v][0] += e.S.F;
                    ps--;
                    //cout << "3\n";
                }else{
                    dp[v][0] += e.S.S;
                    //cout << "4\n";
                }
            }
        }
    }
    while(sz(vs[v]) > k - 1){
        sm[v] -= vs[v].back();
        vs[v].pop_back();
    }
    /*cout << sm[v] << ": ";
    for(auto e : vs[v]){
        cout << e << ' ';
    }
    cout << '\n';*/
    ps = min(sz(vs[v]), k - 1) - 1, cur = min(sz(vs[v]), k - 1);
    dp[v][1] = sm[v] + w;
    for(auto e : ha){
        if(e.F <= 0 || ps < 0){
            dp[v][1] += e.S.S;
        }else{
            if(cur < k - 1){
                cur++;
                dp[v][1] += e.S.F;
            }else{
                if(e.F > vs[v][ps]){
                    dp[v][1] -= vs[v][ps];
                    dp[v][1] += e.S.F;
                    ps--;
                }else{
                    dp[v][1] += e.S.S;
                }
            }
        }
    }
    //cout << dp[v][0] << ' ' << dp[v][1] << '\n';
}

vector<long long> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W) {
    n = _n;
    vector<ll> ans(n, 0);
    for(int i = 0; i < n - 1; i++){
        U[i]++;
        V[i]++;
        g[V[i]].pb({U[i], W[i]});
        g[U[i]].pb({V[i], W[i]});
        ans[0] += W[i];
    }
    k = 1;
    for(; k < min(tresh, n); k++){
        dfs(1, -1, 0);
        ans[k] = ans[0] - dp[1][0];
    }
    vector<int> heavy = {};
    ll ad = 0;
    for(int i = 1; i <= n; i++){
        if(sz(g[i]) > tresh){
            heavy.pb(i);
            for(auto e : g[i]){
                int u = e.F, w = e.S;
                if(sz(g[u]) > tresh){
                    ng[i].pb({u, w});
                }else{
                    vs[i].pb(w);
                }
            }
            sort(all(vs[i]));
            reverse(all(vs[i]));
            for(auto e : vs[i])
                sm[i] += e;
        }else{
            for(auto e : g[i]){
                int u = e.F, w = e.S;
                if(sz(g[u]) <= tresh){
                    ad += w;
                }
            }
        }
    }
    ad /= 2;
    /*for(auto e : heavy){
        cout << e  << ' '  << sm[e] << ": ";
        for(auto u : ng[e]){
            cout << "(" << u.F << ", " << u.S << ") ";
        }
        for(auto u : vs[e]){
            cout << u << ' ';
        }
        cout << '\n';
    }
    cout << ad << "\n";*/
    for(k = n - 1; k >= tresh; k--){
        //cout << k << ":\n";
        ll ret = ad;
        for(auto e : heavy){
            if(!used[e]){
                dfs1(e, -1, 0);
                ret += dp[e][0];
            }
        }
        for(auto e : heavy)
            used[e] = 0;
        ans[k] = ans[0] - ret;
    }
    return ans;
}

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