Submission #684538

#	Time	Username	Problem	Language	Result	Execution time	Memory
684538		CatalinT	Training (IOI07_training)	C++17	100 / 100	51 ms	748 KiB

training

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
 
using namespace std;

using int64 = long long;

struct Edge {
    int x;
    int y;
    int w;
};

const int MAX_N = 1001;

int N, M;

vector<vector<int>> g;
vector<Edge> edges;

vector<int> par;
vector<int> child_idx;

vector<vector<Edge>> has_lca;

int dp_all[MAX_N];
int dp_minus[MAX_N][10];

int depth[MAX_N];

int bst[1<<10];
int dp[1<<10];
int buf[1<<10];

void dfs1(int v, int p) {
    int idx = 0;
    for (auto u : g[v]) if (u != p) {
        depth[u] = depth[v] + 1;
        child_idx[u] = idx++;
        par[u] = v;
        dfs1(u, v);
    }
}


void dfs2(int v, int p) {
    int idx = 0;
    int nchild = 0;
    vector<int> child;
    for (auto u : g[v]) if (u != p) {
        nchild++;
        child.push_back(u);
        dfs2(u, v);
    }

    memset(bst, 0, sizeof(bst));
    memset(buf, 0, sizeof(buf));

    auto best_cost = [&] (int x, int w, int & msk, int & cur) {
        int last = -1;

        cur += dp_all[x];

        while (x != v) {
            last = child_idx[x];
            
            if (par[x] != v) {
                cur += dp_minus[par[x]][last];
            }

            x = par[x];
        }

        msk |= (1<<last);
    };

    vector<int> cand;

    for (auto e : has_lca[v]) {
        int msk = 0;
        int cur = e.w;
        if (e.x != v) {
            best_cost(e.x, e.w, msk, cur);
        }
        if (e.y != v) {
            best_cost(e.y, e.w, msk, cur);
        }

        if (!bst[msk] && cur) {
            cand.push_back(msk);
        }

        assert(msk);

        bst[msk] = max(bst[msk], cur);

        // cerr << (e.x+1) << " / " << (e.y+1) << " -> " << cur << "\n";
    }

    for (auto c : cand) {
        for (int i = 0; i < nchild; i++) {
            if (c >> i & 1) {
                buf[c] += dp_all[child[i]];
            }
        }
    }

    for (int r = 0; r < nchild + 1; r++) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < nchild; i++) {
            if (i == r) continue;
            dp[0] += dp_all[child[i]];
        }

        if (r < nchild)
            dp_minus[v][r] = dp[0];

        dp_all[v] = max(dp_all[v], dp[0]);

        for (int msk = 0; msk < (1<<nchild); msk++) {
            for (auto c : cand) {
                if ((msk & c) == c && !(c & (1<<r))) {
                    // cerr << "=> " << bst[c] << " " << buf[c] << "\n";
                    dp[msk] = max(dp[msk], dp[msk ^ c] + bst[c] - buf[c]);
                    if (r < nchild)
                        dp_minus[v][r] = max(dp_minus[v][r], dp[msk]);
                    dp_all[v] = max(dp_all[v], dp[msk]);
                }
            }
        }
    }

    cerr << v+1 << " " << dp_all[v] << "\n";
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    g.resize(N);
    has_lca.resize(N);
    child_idx.assign(N, -1);

    int tot = 0;

    for (int i = 0; i < M; i++) {
        int x, y, w;
        cin >> x >> y >> w;

        x--;
        y--;
        tot += w;

        if (!w) {
            g[x].push_back(y);
            g[y].push_back(x);
        } else {
            edges.push_back(Edge{x, y, w});
        }
    }
    
    par.assign(N, -1);
    memset(depth, 0, sizeof(depth));
    dfs1(0, 0);

    for (auto e : edges) {
        int x = e.x;
        int y = e.y;

        // cerr << depth[x] << " " << depth[y] << "\n";

        if ((depth[x] & 1) != (depth[y] & 1))
            continue;

        while (depth[x] > depth[y]) {
            x = par[x];
        }

        while (depth[y] > depth[x]) {
            y = par[y];
        }

        while (x != y) {
            x = par[x];
            y = par[y];
        }

        has_lca[x].push_back(e);
        
        cerr << (e.x+1) << ", " << (e.y+1) << " -> " << (x+1) << "\n";
    }

    dfs2(0, 0);

    cout << tot - dp_all[0] << "\n";

    return 0;
}

Compilation message (stderr)

training.cpp: In function 'void dfs2(int, int)':
training.cpp:64:9: warning: unused variable 'idx' [-Wunused-variable]
   64 |     int idx = 0;
      |         ^~~

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