답안 #679941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679941 2023-01-09T16:35:17 Z lorenzoferrari Training (IOI07_training) C++17
100 / 100
82 ms 4956 KB
#include <bits/stdc++.h>
using namespace std;

struct Lca {
    static constexpr int LOG = 10;
    int n;
    vector<int> dep;
    vector<vector<int>> up;

    Lca(int _n, const vector<vector<int>>& adj) : n(_n) {
        dep.assign(n, 0);
        up.assign(n, vector<int>(LOG));
        auto dfs = [&](auto&& self, int v, int p) -> void {
            up[v][0] = p;
            for (int u : adj[v]) {
                if (u == p) continue;
                dep[u] = dep[v] + 1;
                self(self, u, v);
            }
        };
        dfs(dfs, 0, 0);
        for (int i = 1; i < LOG; ++i) {
            for (int j = 0; j < n; ++j) {
                up[j][i] = up[up[j][i-1]][i-1];
            }
        }
    }

    int lift(int v, int k) const {
        for (int i = LOG-1; i >= 0; --i) {
            if (k & (1 << i)) {
                v = up[v][i];
            }
        }
        return v;
    }

    vector<int> get_dep() const { return dep; }
    vector<int> get_par() const {
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = up[i][0];
        }
        return ans;
    }

    int operator()(int a, int b) const {
        if (dep[a] > dep[b]) {
            swap(a, b);
        }
        b = lift(b, dep[b] - dep[a]);
        if (a == b) {
            return a;
        }
        for (int i = LOG-1; i >= 0; --i) {
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
};

int main() {
    int n; cin >> n;
    int m; cin >> m;
    vector<array<int, 3>> e;
    vector<vector<int>> adj(n);
    for (int i = 0, a, b, c; i < m; ++i) {
        cin >> a >> b >> c; --a, --b;
        if (c) {
            e.push_back({a, b, c});
        } else {
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    Lca lca(n, adj);
    auto dep = lca.get_dep();
    auto par = lca.get_par();
    vector<vector<array<int, 3>>> paths(n);
    for (auto [a, b, c] : e) {
        if ((dep[a] & 1) == (dep[b] & 1)) {
            paths[lca(a, b)].push_back({a, b, c});
        }
    }

    constexpr int K = 10;
    constexpr int all = (1 << K) - 1;
    vector<vector<int>> dp(n, vector<int>(1 << 10));
    auto find_child = [&](int anc, int v) -> int {
        int cur = v;
        int prv = -1;
        while (cur != anc) {
            prv = cur;
            cur = par[cur];
        }
        return prv;
    };
    auto find_id = [&](int v, int u) -> int {
        return find(begin(adj[v]), end(adj[v]), u) - begin(adj[v]);
    };
    auto calc = [&](int anc, int v) -> int {
        int ans = dp[v][all];
        int cur = par[v];
        int prv = v;
        while (prv != anc) {
            ans += dp[cur][all ^ (1 << find_id(cur, prv))];
            prv = cur;
            cur = par[cur];
        }
        return ans;
    };
    auto dfs = [&](auto&& self, int v) -> void {
        for (int u : adj[v]) {
            if (u != par[v]) {
                self(self, u);
            }
        }
        vector<array<int, 2>> items;
        for (auto [a, b, c] : paths[v]) {
            if (a == v || b == v) {
                int end = a ^ b ^ v;
                int u = find_child(v, end);
                int i = find_id(v, u);
                items.push_back({1 << i, calc(u, end) + c});
            } else {
                int aa = find_child(v, a);
                int bb = find_child(v, b);
                int ia = find_id(v, aa);
                int ib = find_id(v, bb);
                int mask = (1 << ia) | (1 << ib);
                int inc = c + calc(aa, a) + calc(bb, b);
                items.push_back({mask, inc});
            }
        }
        for (int i = 0; i < (int)adj[v].size(); ++i) {
            if (adj[v][i] == par[v]) continue;
            items.push_back({1 << i, dp[adj[v][i]][all]});
        }
        for (int mask = 0; mask < (1 << K); ++mask) {
            for (int i = 0; i < K; ++i) {
                if (mask & (1 << i)) {
                    dp[v][mask] = max(dp[v][mask], dp[v][mask ^ (1 << i)]);
                }
            }
            for (auto [tmask, w] : items) {
                if ((mask | tmask) == mask) {
                    dp[v][mask] = max(dp[v][mask], dp[v][mask ^ tmask] + w);
                }
            }
        }
    };
    dfs(dfs, 0);

    for (int i = 0; i < n; ++i) {
        // fprintf(stderr, "dp[%d] = %d\n", i+1, dp[i][all]);
    }

    int ans = 0;
    for (auto [_, __, c] : e) {
        ans += c;
    }
    ans -= dp[0][all];
    
    cout << ans << "\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 428 KB Output is correct
2 Correct 4 ms 424 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 4636 KB Output is correct
2 Correct 57 ms 4752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1492 KB Output is correct
2 Correct 17 ms 1492 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2408 KB Output is correct
2 Correct 29 ms 2388 KB Output is correct
3 Correct 31 ms 2456 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 4680 KB Output is correct
2 Correct 64 ms 4692 KB Output is correct
3 Correct 61 ms 4632 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 2460 KB Output is correct
2 Correct 31 ms 2484 KB Output is correct
3 Correct 60 ms 4732 KB Output is correct
4 Correct 32 ms 2516 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 4696 KB Output is correct
2 Correct 82 ms 4692 KB Output is correct
3 Correct 67 ms 4956 KB Output is correct
4 Correct 60 ms 4668 KB Output is correct