Submission #743402

#	Time	Username	Problem	Language	Result	Execution time	Memory
743402		Jarif_Rahman	Road Closures (APIO21_roads)	C++17	0 / 100	2088 ms	35688 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, k;
vector<vector<pair<int, int>>> tree;
vector<int> p;
vector<ll> pe;
vector<int> deg;
vector<int> depth;

vector<ll> dp[2];
vector<vector<int>> forest;
vector<bool> visited;
vector<multiset<ll>> ms;

void pre_dfs(int nd, int ss, int d = 0){
    depth[nd] = d;
    for(auto [x, w]: tree[nd]) if(x != ss){
        pre_dfs(x, nd, d+1);
        p[x] = nd;
        pe[x] = w;
        ms[nd].insert(w);
    }
}

void dfs(int nd){
    visited[nd] = 1;
    ll sum = 0;
    for(int x: forest[nd]){
        dfs(x);
        sum+=dp[1][x];
        ms[nd].insert(-dp[1][x]+min(dp[0][x], dp[1][x])+pe[x]);
    }

    dp[0][nd] = sum, dp[1][nd] = sum;

    int c = ms[nd].size();
    if(c-k > 0){
        auto it = ms[nd].begin();
        for(int i = 0; i < c-k; i++) dp[0][nd]+=*it, it++;
    }
    if(c-k+1 > 0){
        auto it = ms[nd].begin();
        for(int i = 0; i < c-k+1; i++) dp[1][nd]+=*it, it++;
    }

    for(int x: forest[nd]){
        ms[nd].erase(ms[nd].find(-dp[1][x]+min(dp[0][x], dp[1][x])+pe[x]));
    }
}

vector<ll> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W){
    swap(n, _n);
    tree.resize(n);
    p.assign(n, -1);
    pe.resize(n);
    deg.assign(n, 0);
    depth.resize(n);

    fill(dp, dp+2, vector<ll>(n, 0));
    forest.resize(n);
    visited.assign(n, 0);
    ms.resize(n);

    for(int i = 0; i < n-1; i++){
        deg[U[i]]++, deg[V[i]]++;
        tree[U[i]].pb({V[i], W[i]});
        tree[V[i]].pb({U[i], W[i]});
    }

    pre_dfs(0, -1);

    vector<int> o(n);
    for(int i = 0; i < n; i++) o[i] = i;
    sort(o.begin(), o.end(), [&](int a, int b){
        return deg[a] > deg[b];
    });

    vector<ll> ans(n, 0);
    for(int w: W) ans[0]+=w;
    for(k = n-1; k > 0; k--){
        vector<int> nodes;
        for(int i = 0; i < n; i++){
            if(deg[o[i]] <= k) break;
            nodes.pb(o[i]);
            if(deg[p[o[i]]] > k){
                forest[p[o[i]]].pb(o[i]);
                ms[p[o[i]]].erase(ms[p[o[i]]].find(pe[o[i]]));
            }
        }

        sort(nodes.begin(), nodes.end(), [&](int a, int b){
            return depth[a] < depth[b];
        });

        for(int nd: nodes) if(!visited[nd]) dfs(nd), ans[k]+=dp[0][nd];

        for(int nd: nodes){
            forest[nd].clear();
            visited[nd] = 0;
            if(deg[p[nd]] > k){
                ms[p[nd]].insert(pe[nd]);
            }
        }
    }

    return ans;
}

• 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