Submission #762096

#	Time	Username	Problem	Language	Result	Execution time	Memory
762096		caganyanmaz	Training (IOI07_training)	C++17	0 / 100	43 ms	62684 KiB

training

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

constexpr static int SIZE = 1000;
constexpr static int LOG_SIZE = 11;
constexpr static int SUBTREE_SIZE = 11;
vector<int> g[SIZE];
vector<array<int, 3>> lower_children[SIZE];
int dp[SIZE][SUBTREE_SIZE][SIZE+1]; // current_node, closed subtree (open if 10), last_blocking (if equal to n it means no blocking
int best[SIZE][SUBTREE_SIZE][SIZE][SUBTREE_SIZE]; // Highest cost connection from subtree to subtree (given subtree is closed)
int depth[SIZE];
vector<array<int, 3>> edges;
int mapping[SIZE];
int n;


struct LCA
{
        int bl[SIZE][LOG_SIZE];
        void construct()
        {
                for (int i = 1; i < LOG_SIZE; i++)
                        for (int j = 0; j < n; j++)
                                bl[j][i] = bl[bl[j][i-1]][i-1];
        }
        int advance(int node, int k)
        {
                for (int i = 0; i < LOG_SIZE; i++)
                        if ((1<<i)&k)
                                node = bl[node][i];
                return node;
        }
        void equalize_depths(int& a, int& b)
        {
                if (depth[a] > depth[b])
                        a = advance(a, depth[a]-depth[b]);
                else if (depth[b] > depth[a])
                        b = advance(b, depth[b]-depth[a]);
        }
        array<int, 2> get_subtree_pair(int a, int b)
        {
                equalize_depths(a, b);
                for (int i = LOG_SIZE-1; i >= 0; i--)
                        if (bl[a][i] != bl[b][i])
                                a = bl[a][i], b = bl[b][i];
                return array<int,2>({a,b});
        }
        int get(int a, int b)
        {
                equalize_depths(a, b);
                if (a == b)
                        return a;
                else
                        return bl[get_subtree_pair(a, b)[0]][0];
        }
        int parent(int node)
        {
                return bl[node][0];
        }
};

LCA lca;
int sort_children(int node, int parent);

void dfs1(int node, int parent)
{
        if (parent == -1)
        {
                depth[node] = 0;
                lca.bl[node][0] = node;
        }
        else
        {
                depth[node] = depth[parent] + 1;
                lca.bl[node][0] = parent;
        }
        for (int c : g[node])
                if (c != parent)
                        dfs1(c, node);
        sort_children(node, parent);

}

int get_proper_subtree(int node, int subtree)
{
        int parent = lca.parent(subtree);
        if (depth[node] == depth[subtree])
                return -1;
        int below = lca.advance(node, depth[node] - depth[subtree] - 1);
        return mapping[below];
}

// O(n)
void process_edges()
{
        for (auto [a, b, c] : edges)
        {
                if ((depth[a]+depth[b])&1)
                        continue;
                if (depth[a] > depth[b])
                        swap(a, b);
                if (lca.get(a, b) == a)
                {
                        int proper_subtree = mapping[lca.advance(b, depth[b] - depth[a] - 1)];
                        lower_children[a].pb({a, c, proper_subtree});
                }
                else
                {
                        auto [ast, bst] = lca.get_subtree_pair(a, b);
                        int apst = get_proper_subtree(a, ast), bpst = get_proper_subtree(b, bst);
                        for (int i = 0; i < SUBTREE_SIZE; i++)
                                for (int j = 0; j < SUBTREE_SIZE; j++)
                                        if (i != apst && j != bpst)
                                                best[ast][i][bst][j] = max(best[ast][i][bst][j], c);
                }
        }
}

int sort_children(int node, int parent)
{
        for (int i = 0; i < g[node].size(); i++)
        {
                if (g[node][i] == parent)
                {
                        swap(g[node].back(), g[node][i]);
                        break;
                }
        }
        int last = g[node].size();
        if (parent != -1)
                last--;
        sort(g[node].begin(), g[node].begin() + last);
        for (int i = 0; i < last; i++)
                mapping[g[node][i]] = i;
        return last;
}

void dfs2(int node, int parent)
{
        for (int c : g[node])
                if (c != parent)
                        dfs2(c, node);
        sort_children(node, parent);
        int last = sort_children(node, parent);
        vector<vector<int>> best_pairs(last, vector<int>(last));
        for (int i = 0; i < last; i++)
        {
                for (int j = 0; j < SUBTREE_SIZE; j++)
                {
                        best_pairs[i][i] = max(best_pairs[i][i], dp[g[node][i]][j][n]);
                        for (int k = i+1; k < last; k++)
                        {
                                for (int l = 0; l < SUBTREE_SIZE; l++)
                                {
                                        int val =  dp[g[node][i]][j][n] + dp[g[node][k]][l][n] + best[g[node][i]][j][g[node][k]][l];
                                        best_pairs[i][k] = max(best_pairs[i][k], val);
                                }
                        }
                }
        }
        vector<int> pdp(1<<last);
        for (int i = 0; i < pdp.size(); i++)
                for (int j = 0; j < last; j++)
                        for (int k = j; k < last; k++)
                                if (!(i&(1<<j)) && !(i&(1<<k)))
                                        pdp[i|(1<<j)|(1<<k)] = max(pdp[i|(i<<j)|(1<<k)], pdp[i] + best_pairs[j][k]);
        for (int i = 0; i < n; i++)
                if (i != node)
                        for (int j = 0; j < last; j++)
                                dp[node][SUBTREE_SIZE-1][i] = max(dp[node][SUBTREE_SIZE-1][i], dp[g[node][j]][SUBTREE_SIZE-1][i] + pdp[((1<<last)-1)^(1<<j)]);
        dp[node][SUBTREE_SIZE-1][n] = max(dp[node][SUBTREE_SIZE-1][n], pdp[(1<<last)-1]);
        for (auto [lc, c, pst] : lower_children[node])
                for (int i = 0; i < last; i++)
                        dp[node][pst][n] = max(dp[node][pst][n], pdp[((1<<last)-1)^(1<<i)] + dp[g[node][i]][SUBTREE_SIZE-1][lc] + c);
        for (int i = 0; i < SUBTREE_SIZE; i++)
                dp[node][i][node] = dp[node][i][n];
}

int main()
{
        int m;
        cin >> n >> m;
        int total_cost = 0;
        while (m--)
        {
                int a, b, c;
                cin >> a >> b >> c;
                a--, b--;
                if (c == 0)
                {
                        g[a].pb(b);
                        g[b].pb(a);
                }
                else
                {
                        edges.pb({a, b, c});
                        total_cost += c;
                }

        }
        dfs1(0, -1);
        lca.construct();
        process_edges();
        dfs2(0, -1);
        int reduction = 0;
        for (int i = 0; i < SUBTREE_SIZE; i++)
                reduction = max(reduction, dp[0][i][0]);
        cout << (total_cost - reduction) << "\n";
}

Compilation message (stderr)

training.cpp: In function 'int get_proper_subtree(int, int)':
training.cpp:87:13: warning: unused variable 'parent' [-Wunused-variable]
   87 |         int parent = lca.parent(subtree);
      |             ^~~~~~
training.cpp: In function 'int sort_children(int, int)':
training.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < g[node].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int, int)':
training.cpp:163:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for (int i = 0; i < pdp.size(); i++)
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9