Submission #1074133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074133		Kerim	Road Closures (APIO21_roads)	C++17	100 / 100	627 ms	81208 KiB

roads

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define mp(x, y) make_pair(x, y)
using namespace __gnu_pbds;
using namespace std;
 
using ll = long long;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

 
#define ff  first
#define ss  second
#define pii pair<int, int>
const ll B = 1e18;
vector<bool> vis;
vector<vector<ll>> dp;
vector<vector<pair<int, pii>>> E;
vector<vector<ll>> F, C;
vector<ordered_set> OS;
vector<int> deg;
map<pair<int,int>, int> weight;

void upd(int x, int p, int v){
    if (v < 0) //remove
        OS[x].erase(p);
    else //add
        OS[x].insert(p);
    int sz = F[x].size();
    for (;p < sz; p += p&(-p))
        F[x][p] += v;
}

ll get(int x, int k){
    if (k == 0)
        return 0;
    if (OS[x].size() < k)
        return B;
    int p = *OS[x].find_by_order(k-1);
    ll res = 0;
    for (;p; p -= p&(-p))
        res += F[x][p];
    return res;
}

void dfs(int x, int k, bool f, int p = -1) {
    vis[x] = true;
 
    if (dp[x][f] == B) 
        dp[x][f] = 0;
    else 
        return;
 
    vector<pii> history;
    vector<ll> v;
    int pos = lower_bound(E[x].begin(), E[x].end(), mp(k, mp(-1, -1))) - E[x].begin();
    //consider only children with deg >= k
    for (; pos < E[x].size(); pos++){
        int i = E[x][pos].ss.ss;
        int value = E[x][pos].ss.ff;
        int weight = C[x][pos];
        if (i == p) continue;
        dfs(i, k, 0, x);
        dfs(i, k, 1, x);
        dp[x][f] += dp[i][0];
        v.push_back({dp[i][1] - dp[i][0]});
        upd(x, weight, -value);
        history.push_back({weight, value});
    }
    if (~p){
        int w = weight[{x, p}];
        pos = lower_bound(E[x].begin(), E[x].end(), mp(deg[p], mp(w, p))) - E[x].begin();
        int value = E[x][pos].ss.ff;
        int weight = C[x][pos];
        upd(x, weight, -value);
        history.push_back({weight, value});
        if (f == 1)
            dp[x][f] += w;
    }
    
    sort(v.begin(), v.end());
 
    int i = 0, cnt = (int)E[x].size() - k - f;
    while (i < (int)v.size() and v[i] < 0)
        cnt -= 1, dp[x][f] += v[i++];
    cnt = max(cnt, 0);

    ll answer = B, sum = 0;
    for (; i <= int(v.size()) and cnt >= 0; i++) {
        answer = min(answer, sum + get(x, cnt));
        if (i < v.size())
            sum += v[i];
        cnt -= 1;
    }

    dp[x][f] += answer;
    
    //Recovery
    for (auto [a, b]: history)
        upd(x, a, b);
}
 
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
    E.assign(n, {});
    C.assign(n, {});
    F.assign(n, {});
    OS.assign(n, {});
    deg.assign(n, 0);
    weight.clear();
 
    vector<ll> ans = {0};
    for (int i = 0; i < n - 1; i++) {
        ans[0] += W[i];
        weight[{U[i], V[i]}] = weight[{V[i], U[i]}] = W[i];
        deg[U[i]] += 1; deg[V[i]] += 1;
    }
    for (int i = 0; i < n-1; i++){
        E[U[i]].push_back({deg[V[i]], {W[i], V[i]}});
        E[V[i]].push_back({deg[U[i]], {W[i], U[i]}});
    }
    for (int i = 0; i < n; i++)
        sort(E[i].begin(), E[i].end());
    
    //Initial values are given for all sets
    for (int i = 0; i < n; i++){
        int sz = (int)E[i].size();
        //compress the values of each set
        vector<pii> values;
        for (int j = 0; j < sz; j++)
            values.push_back({E[i][j].ss.ff, j});
        sort(values.begin(), values.end());
        F[i].resize(sz+1); C[i].resize(sz);
        for (int j = 0; j < sz; j++){
            upd(i, j+1, values[j].first);
            C[i][values[j].second] = j+1;
        }
    }
 
    vector<pii> v;
    for (int i = 0; i < n; i++) 
        v.push_back({(int)E[i].size(), i});
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
 
    vis.assign(n, false);
    dp.assign(n, vector<ll>(2, B));
    for (int i = 1; i < n; i++) {
        while (!v.empty() and v.back().ff < i) v.pop_back();
        for (auto j : v) {
            vis[j.ss] = false;
            dp[j.ss][0] = dp[j.ss][1] = B;
        }
        ll sm = 0;
        for (auto j : v) {
            if (vis[j.ss]) continue;
            dfs(j.ss, i, 0);
            sm += dp[j.ss][0];
        }
    
        ans.push_back(sm);
    }
 
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'll get(int, int)':
roads.cpp:40:22: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (OS[x].size() < k)
      |         ~~~~~~~~~~~~~^~~
roads.cpp: In function 'void dfs(int, int, bool, int)':
roads.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (; pos < E[x].size(); pos++){
      |            ~~~~^~~~~~~~~~~~~
roads.cpp:94:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         if (i < v.size())
      |             ~~^~~~~~~~~~

• 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