Submission #521457

#	Time	Username	Problem	Language	Result	Execution time	Memory
521457		maomao90	Road Closures (APIO21_roads)	C++17	0 / 100	218 ms	46768 KiB

roads

// Fight the good fight of the faith. Take hold of the 
// eternal life to which you were called when you made 
// your good confession in the presence of many witnesses
// 1 Timonthy 6:12
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int n;
vii tadj[MAXN], adj[MAXN];
vi deg[MAXN];
bool on[MAXN];
multiset<int> offw[MAXN];
set<int> useful;
bool vis[MAXN];

int k;
// first is never close parent, second is close parent
pll dp(int u, int p) {
    vector<pll> vec;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        vis[v] = 1;
        auto [a, b] = dp(v, u);
        b += w;
        vec.pb(MP(a, b));
    }
    sort(ALL(vec), [&] (pll l, pll r) {
            return l.SE - l.FI < r.SE - r.FI;
            });
    auto solve = [&] (int k) {
        ll res = INF, cur = 0;
        int sze = offw[u].size();
        for (auto [a, b] : vec) {
            cur += a;
            sze++;
        }
        int j = 0;
        for (; j < vec.size() && sze > k; j++) {
            auto [a, b] = vec[j];
            cur -= a;
            cur += b;
            sze--;
        }
        auto ptr = offw[u].begin();
        while (sze > k && ptr != offw[u].end()) {
            cur += *ptr;
            sze--;
        }
        if (sze > k) {
            return LINF;
        }
        res = cur;
        for (; j < vec.size() && ptr != offw[u].begin(); j++) {
            auto [a, b] = vec[j];
            cur -= a;
            cur += b;
            ptr = prev(ptr);
            cur -= *ptr;
            mnto(res, cur);
        }
        return res;
    };
    return MP(solve(k - 1), solve(k));
}

vll minimum_closure_costs(int n, vi u, vi v, vi w) {
    ::n = n;
    REP (i, 0, n - 1) {
        tadj[u[i]].pb(MP(v[i], w[i]));
        tadj[v[i]].pb(MP(u[i], w[i]));
    }
    REP (i, 0, n) {
        deg[tadj[i].size()].pb(i);
    }
    vll ans(n, 0);
    RREP (k, n - 1, 0) {
        ::k = k;
        debug("%d\n", k);
        for (int i : deg[k + 1]) {
            debug(" %d\n", i);
            useful.insert(i);
            on[i] = 1;
            for (auto [u, w] : tadj[i]) {
                if (on[u]) {
                    adj[u].pb(MP(i, w));
                    adj[i].pb(MP(u, w));
                    offw[u].erase(offw[u].find(w));
                } else {
                    offw[i].insert(w);
                }
            }
        }
        for (int i : useful) {
            if (vis[i]) continue;
            vis[i] = 1;
            auto [a, b] = dp(i, -1);
            ans[k] = b;
        }
        for (int i : useful) {
            vis[i] = 0;
        }
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (; j < vec.size() && sze > k; j++) {
      |                ~~^~~~~~~~~~~~
roads.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (; j < vec.size() && ptr != offw[u].begin(); j++) {
      |                ~~^~~~~~~~~~~~

• 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