oj.uz

Submission #489770

# Submission time Handle Problem Language Result Execution time Memory
489770 2021-11-24T15:04:29 Z dung11112003 Road Closures (APIO21_roads) C++11
22 / 100
 270 ms 45700 KB 
#include "roads.h"

#include <bits/stdc++.h>

using namespace std;

vector <long long> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W)
{
    int n = N;
    vector <vector <array <int, 3>>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u = U[i], v = V[i], w = W[i];
        adj[u].push_back({v, w, 0});
        adj[v].push_back({u, w, 0});
    }
    struct FenwickTree
    {
        //1 - indexed
        int n;
        vector <int> f;
        vector <long long> g;
        FenwickTree () : n(0), f(), g() {};
        FenwickTree (int n) : n(n), f(n + 1), g(n + 1) {};
        void insert(int x, long long d)
        {
            for (; x <= n; x += x & -x)
            {
                f[x]++;
                g[x] += d;
            }
        }
        int size()
        {
            int x = n, sum = 0;
            for (; x; x &= x - 1)
            {
                sum += f[x];
            }
            return sum;
        }
        long long prefix_kth(int k)
        {
            int idx = 0;
            long long sum = 0;
            for (int mask = 1 << 20; mask; mask >>= 1)
            {
                if (idx + mask <= n && f[idx + mask] <= k)
                {
                    idx += mask;
                    k -= f[idx];
                    sum += g[idx];
                }
            }
            return sum;
        }
    };
    vector <FenwickTree> f(n);
    for (int i = 0; i < n; i++)
    {
        sort(adj[i].begin(), adj[i].end(), [](const array <int, 3> &x, const array <int, 3> &y)
        {
            return x[1] < y[1];
        });
        f[i] = FenwickTree(adj[i].size());
        for (int j = 0; j < (int)adj[i].size(); j++)
        {
            adj[i][j][2] = j + 1;
        }
    }
    vector <int> sorted_deg(n);
    iota(sorted_deg.begin(), sorted_deg.end(), 0);
    sort(sorted_deg.begin(), sorted_deg.end(), [&](int x, int y)
    {
        return adj[x].size() < adj[y].size();
    });
    vector <int> erased(n);
    set <int> not_erased;
    vector <int> flag(n);
    for (int i = 0; i < n; i++)
    {
        not_erased.insert(i);
    }
    int id = 0;
    vector <array <long long, 2>> dp(n);
    vector <long long> ans(n);
    const long long inf = 1e15;
    ans[0] = accumulate(W.begin(), W.end(), 0LL);
    vector <int> deg(n);
    for (int i = 0; i < n; i++)
    {
        deg[i] = (int)adj[i].size();
    }
    for (int k = 1; k < n; k++)
    {
        vector <int> pending;
        while (id < n && (int)deg[sorted_deg[id]] < k)
        {
            int u = sorted_deg[id];
            //remove u
            for (auto &e: adj[u])
            {
                pending.push_back(e[0]);
            }
            erased[u] = 1;
            not_erased.erase(u);
            adj[u].clear();
            id++;
        }
        sort(pending.begin(), pending.end());
        pending.resize(unique(pending.begin(), pending.end()) - pending.begin());
        for (auto &u: pending)
        {
            vector <array <int, 3>> new_adj;
            for (auto &e: adj[u])
            {
                int v = e[0];
                if (erased[v])
                {
                    f[u].insert(e[2], e[1]);
                }
                else
                {
                    new_adj.push_back(e);
                }
            }
            adj[u].swap(new_adj);
        }
        function <void (int)> dfs([&](int u)
        {
            flag[u] = 1;
            dp[u][0] = dp[u][1] = inf;
            long long sum[2] = {};
            vector <long long> vec;
            for (auto &e: adj[u])
            {
                int v = e[0], w = e[1];
                if (!flag[v])
                {
                    dfs(v);
                    sum[0] += dp[v][0];
                    sum[1] += dp[v][0];
                    vec.push_back(dp[v][1] + w - dp[v][0]);
                }
            }
            sort(vec.begin(), vec.end());
            partial_sum(vec.begin(), vec.end(), vec.begin());
            int need = (int)deg[u] - k, cnt = f[u].size();
            if (cnt >= need)
            {
                dp[u][0] = min(dp[u][0], f[u].prefix_kth(need) + sum[0]);
            }
            if (cnt >= need - 1)
            {
                dp[u][1] = min(dp[u][1], f[u].prefix_kth(need - 1) + sum[1]);
            }
            for (int i = 0; i < (int)vec.size(); i++)
            {
                if (cnt + i + 1 >= need && i + 1 <= need)
                {
                    dp[u][0] = min(dp[u][0], sum[0] + vec[i] + f[u].prefix_kth(need - i - 1));
                }
                if (cnt + i + 1 >= need - 1 && i + 1 <= need - 1)
                {
                    dp[u][1] = min(dp[u][1], sum[1] + vec[i] + f[u].prefix_kth(need - 1 - i - 1));
                }
            }
        });
        for (auto &u: not_erased)
        {
            if (!flag[u])
            {
                dfs(u);
                ans[k] += dp[u][0];
            }
        }
        for (auto &u: not_erased)
        {
            flag[u] = 0;
        }
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 932 KB Output is correct
4 Correct 3 ms 932 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 108 ms 19580 KB Output is correct
13 Correct 156 ms 32628 KB Output is correct
14 Correct 146 ms 29148 KB Output is correct
15 Correct 194 ms 32120 KB Output is correct
16 Correct 172 ms 32628 KB Output is correct
17 Correct 196 ms 32540 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 142 ms 29540 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 116 ms 37976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 29412 KB Output is correct
2 Correct 267 ms 29004 KB Output is correct
3 Correct 197 ms 32128 KB Output is correct
4 Correct 270 ms 30356 KB Output is correct
5 Correct 177 ms 32216 KB Output is correct
6 Correct 163 ms 31276 KB Output is correct
7 Correct 206 ms 30916 KB Output is correct
8 Correct 153 ms 30220 KB Output is correct
9 Correct 224 ms 35972 KB Output is correct
10 Correct 250 ms 29768 KB Output is correct
11 Correct 201 ms 31968 KB Output is correct
12 Correct 161 ms 31728 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 131 ms 41176 KB Output is correct
15 Correct 140 ms 45700 KB Output is correct
16 Correct 3 ms 844 KB Output is correct
17 Correct 5 ms 844 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 3 ms 924 KB Output is correct
20 Correct 4 ms 844 KB Output is correct
21 Correct 150 ms 29580 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 29412 KB Output is correct
2 Correct 267 ms 29004 KB Output is correct
3 Correct 197 ms 32128 KB Output is correct
4 Correct 270 ms 30356 KB Output is correct
5 Correct 177 ms 32216 KB Output is correct
6 Correct 163 ms 31276 KB Output is correct
7 Correct 206 ms 30916 KB Output is correct
8 Correct 153 ms 30220 KB Output is correct
9 Correct 224 ms 35972 KB Output is correct
10 Correct 250 ms 29768 KB Output is correct
11 Correct 201 ms 31968 KB Output is correct
12 Correct 161 ms 31728 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 131 ms 41176 KB Output is correct
15 Correct 140 ms 45700 KB Output is correct
16 Correct 3 ms 844 KB Output is correct
17 Correct 5 ms 844 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 3 ms 924 KB Output is correct
20 Correct 4 ms 844 KB Output is correct
21 Correct 150 ms 29580 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Incorrect 206 ms 26016 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 932 KB Output is correct
4 Correct 3 ms 932 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 108 ms 19580 KB Output is correct
13 Correct 156 ms 32628 KB Output is correct
14 Correct 146 ms 29148 KB Output is correct
15 Correct 194 ms 32120 KB Output is correct
16 Correct 172 ms 32628 KB Output is correct
17 Correct 196 ms 32540 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 142 ms 29540 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Incorrect 116 ms 37976 KB Output isn't correct
22 Halted 0 ms 0 KB -