oj.uz

Submission #522103

# Submission time Handle Problem Language Result Execution time Memory
522103 2022-02-03T20:32:19 Z blue Road Closures (APIO21_roads) C++17
14 / 100
 2000 ms 33900 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const ll INF = 1'000'000'000'000'000'000LL;


int N;
vi U, V, W;

vi edge[mx];
vi deg(mx, 0);
vi deg_occ[mx];

vi depth(mx);
vi parent(mx, -1);

ll wt_sum = 0;

vi par_wt(mx);



void dfs1(int u, int p)
{
    for(int e: edge[u])
    {
        int v = U[e] + V[e] - u;
        int w = W[e];
        if(v == p) continue;

        par_wt[v] = w;

        depth[v] = depth[u] + 1;
        parent[v] = u;
        dfs1(v, u);
    }
}





struct DS
{
    multiset<ll> values;

    ll minSum(int z)
    {
        if(z > sz(values)) return INF;

        if(z <= 0) return 0;

        int ct = 0;
        ll res = 0;

        for(ll v : values)
        {
            res += v;
            ct++;
            if(ct == z) break;
        }

        return res;
    }

    void insert(ll v) 
    {
        values.insert(v);
    }

    int size()
    {
        return sz(values);
    }
};







vll minimum_closure_costs(int N_, vi U_, vi V_, vi W_)
{   
    N = N_;
    U = U_;
    V = V_;
    W = W_;

    for(int e = 0; e < N-1; e++)
    {
        edge[U[e]].push_back(e);
        edge[V[e]].push_back(e);

        deg[U[e]]++;
        deg[V[e]]++;

        wt_sum += W[e];
    }

    for(int i = 0; i < N; i++)
        deg_occ[deg[i]].push_back(i);

    for(int i = 0; i < N; i++)
    {
        sort(edge[i].begin(), edge[i].end(), [] (int e, int f)
        {
            return deg[U[e]] + deg[V[e]] > deg[U[f]] + deg[V[f]];
        });
    }


    dfs1(0, -1);

    set<pii> it_list;

    for(int i = 0; i < N; i++) it_list.insert({-depth[i], i});


    vll res(N, 0);

    res[0] = wt_sum;

                     // root deg <= K-1
    vll dp0(N), dp1(N);
    //root deg <= K

    DS extra_edges[N];

    vi intdeg = deg;
    for(int i = 1; i < N; i++)
        intdeg[i]--;

    for(int k = 1; k < N; k++)
    {
        cerr << "\n\n\n\n\n";
        cerr << "k = " << k << '\n';
        for(int u: deg_occ[k]) //deg_occ[0] is empty
        {
            cerr << "eliminating " << u << '\n';
            it_list.erase({-depth[u], u});
            for(int e : edge[u])
            {
                int v = U[e] + V[e] - u;
                int w = W[e];
                if(parent[v] != u)
                    extra_edges[v].insert(w);
                // cerr << "extra edges " << v << " -> insert " << w << '\n';
            }
        }

        for(auto p: it_list)
        {
            cerr << "\n\n";
            int u = p.second;
            cerr << "u = " << u << '\n';

            cerr << "ee = ";
            for(ll y : extra_edges[u].values) cerr << y << ' ';
                cerr << '\n';

            dp0[u] = dp1[u] = INF;

            ll basicCost = 0;

            vector<ll> upgrades;

            for(auto e: edge[u])
            {
                int v = U[e] + V[e] - u;
                ll w = W[e];

                if(v == parent[u]) continue;

                if(deg[v] <= k) break;

                basicCost += dp1[v];
                upgrades.push_back(dp0[v] + w - dp1[v]);
            }

            sort(upgrades.begin(), upgrades.end());

            ll upgrade_total = 0;

            dp0[u] = min(dp0[u], basicCost + extra_edges[u].minSum(intdeg[u] - k));
            dp1[u] = min(dp1[u], basicCost + extra_edges[u].minSum(intdeg[u] - (k-1)));

            cerr << "pre : " << dp0[u] << ' ' << dp1[u] << '\n';

            // cerr << basicCost << '\n';

            // cerr << "ee size = " << sz(extra_edges[u]) << ", query val = " << intdeg[u] - k << '\n';




            for(int cct = 0; cct < sz(upgrades); cct++)
            {
                // cerr << "cct = " << cct << '\n';
                upgrade_total += upgrades[cct];
                dp0[u] = min(dp0[u], basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - k - (cct+1)));
                dp1[u] = min(dp1[u], basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - (k-1) - (cct+1)));
                cerr << "! " << intdeg[u] - k - (cct+1) << ' ' << intdeg[u] - (k-1) - (cct+1) << '\n';
                cerr << cct << " , " << basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - k - (cct+1)) << ' ' << basicCost + upgrade_total + extra_edges[u].minSum(intdeg[u] - (k-1) - (cct+1)) << '\n';
            }

            if(u == 0) 
            {
                    // cerr << "adding " << dp0[u] << " a to res " << k << '\n'; 
                res[k] += dp0[u];
            }
            else if(deg[parent[u]] <= k)
            {
                // cerr << "adding " << min(dp1[u], dp0[u] + par_wt[u]) << " b to res " << k << '\n'; 
                res[k] += min(dp1[u], dp0[u] + par_wt[u]);
            }

            cerr << u << " : " << parent[u] << ' ' << dp0[u] << ' ' << dp1[u] << '\n';
        }
    }


    return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Execution timed out 2076 ms 16700 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6860 KB Output is correct
2 Execution timed out 2092 ms 33900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6860 KB Output is correct
2 Correct 3 ms 6860 KB Output is correct
3 Correct 3 ms 6860 KB Output is correct
4 Correct 10 ms 6996 KB Output is correct
5 Correct 12 ms 6988 KB Output is correct
6 Correct 18 ms 7020 KB Output is correct
7 Correct 11 ms 7016 KB Output is correct
8 Correct 19 ms 7032 KB Output is correct
9 Correct 17 ms 6988 KB Output is correct
10 Correct 11 ms 6988 KB Output is correct
11 Correct 11 ms 6988 KB Output is correct
12 Correct 12 ms 7028 KB Output is correct
13 Correct 49 ms 7164 KB Output is correct
14 Correct 106 ms 7532 KB Output is correct
15 Correct 110 ms 7380 KB Output is correct
16 Correct 8 ms 6988 KB Output is correct
17 Correct 13 ms 7004 KB Output is correct
18 Correct 15 ms 7008 KB Output is correct
19 Correct 87 ms 7024 KB Output is correct
20 Correct 98 ms 7044 KB Output is correct
21 Correct 4 ms 6988 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6860 KB Output is correct
2 Correct 3 ms 6860 KB Output is correct
3 Correct 3 ms 6860 KB Output is correct
4 Correct 10 ms 6996 KB Output is correct
5 Correct 12 ms 6988 KB Output is correct
6 Correct 18 ms 7020 KB Output is correct
7 Correct 11 ms 7016 KB Output is correct
8 Correct 19 ms 7032 KB Output is correct
9 Correct 17 ms 6988 KB Output is correct
10 Correct 11 ms 6988 KB Output is correct
11 Correct 11 ms 6988 KB Output is correct
12 Correct 12 ms 7028 KB Output is correct
13 Correct 49 ms 7164 KB Output is correct
14 Correct 106 ms 7532 KB Output is correct
15 Correct 110 ms 7380 KB Output is correct
16 Correct 8 ms 6988 KB Output is correct
17 Correct 13 ms 7004 KB Output is correct
18 Correct 15 ms 7008 KB Output is correct
19 Correct 87 ms 7024 KB Output is correct
20 Correct 98 ms 7044 KB Output is correct
21 Correct 4 ms 6988 KB Output is correct
22 Correct 3 ms 6860 KB Output is correct
23 Correct 56 ms 7340 KB Output is correct
24 Correct 88 ms 7620 KB Output is correct
25 Correct 77 ms 7424 KB Output is correct
26 Correct 181 ms 7608 KB Output is correct
27 Correct 1464 ms 13908 KB Output is correct
28 Correct 1536 ms 8880 KB Output is correct
29 Correct 91 ms 7480 KB Output is correct
30 Correct 293 ms 8516 KB Output is correct
31 Correct 264 ms 8344 KB Output is correct
32 Execution timed out 2066 ms 17380 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 30596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 30596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6860 KB Output is correct
2 Execution timed out 2076 ms 16700 KB Time limit exceeded
3 Halted 0 ms 0 KB -