Submission #898461

#	Time	Username	Problem	Language	Result	Execution time	Memory
898461		RedGrey1993	Training (IOI07_training)	C++17	100 / 100	31 ms	12908 KiB

training

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, const pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
template <unsigned int MOD>
class ModInt {
public:
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
 
using Mint2 = ModInt<mod-1>;

class Solution {
    struct Edge {
        int u,v;
        int cost;
        friend ostream &operator<<(ostream &os, const Edge &r) { 
            return os << r.u << "-->" << r.v << ":" << r.cost; 
        }
    };
    struct LCA {
        int node;
        int son1=-1, son2=-1;
        friend ostream &operator<<(ostream &os, const LCA &r) { 
            return os << r.node << "(" << r.son1 << ", " << r.son2 << ")"; 
        }
    };
public:
    void Solve() {
        int n,m;
        // n<=1000, m<=5000
        while(cin>>n>>m) {
            int total_cost = 0;

            vi degree(n);
            vector<vi> tree_edges(n);
            vector<Edge> edges;
            int u,v,c;
            rep(i,0,m) {
                cin>>u>>v>>c;
                u--; v--;

                degree[u]++; degree[v]++;
                if (c == 0) {
                    tree_edges[u].emplace_back(v);
                    tree_edges[v].emplace_back(u);
                } else {
                    edges.emplace_back(Edge{u,v,c});
                    total_cost += c;
                }
            }

            int max_edge_num = 1;
            rep(i,0,n) max_edge_num = *max_element(all(degree));

            vector<vi> tree_path_len(n, vi(n));
            int root = 0;
            function<void(int,int,int)> dfs1 = [&] (int u, int p, int d) {
                tree_path_len[root][u] = d;
                for (int v : tree_edges[u]) {
                    if (v != p) dfs1(v, u, d+1);
                }
            };
            // O(n*m)
            for (root = 0; root < n; root++) {
                dfs1(root, -1, 0);
            }

            // dbg(tree_path_len);
            vector<Edge> even_edges;
            for (auto edge : edges) {
                if (tree_path_len[edge.u][edge.v] % 2 == 0) {
                    even_edges.emplace_back(edge);
                }
            }

            dbg(even_edges);

            int max_d = 1;
            while ((1<<max_d) <= n) {
                max_d++;
            }

            vector<vi> parent(n, vi(max_d));
            vi nth_son(n);
            function<void(int,int)> dfs2 = [&] (int u, int p) {
                // for (int v : tree_edges[u]) {
                rep(i,0,sz(tree_edges[u])) {
                    int v = tree_edges[u][i];
                    if (v != p) {
                        parent[v][0] = u;
                        nth_son[v] = i;
                        dfs2(v, u);
                    }
                }
            };
            parent[0][0] = -1;
            nth_son[0] = -1;
            dfs2(0, -1);
            // O(nlogn)
            rep(d,1,max_d) {
                rep(u, 0, n) {
                    if (parent[u][d-1] == -1) parent[u][d] = -1;
                    else parent[u][d] = parent[parent[u][d-1]][d-1];
                }
            }
            dbg(parent);
            dbg(nth_son);

            auto get_depth = [&] (int idx) {
                int depth = 0;
                int d = sz(parent[0]) - 1;
                while(idx != 0) {
                    // dbg(mp(idx, d));
                    if (parent[idx][d] != -1) {
                        depth |= (1<<d);
                        idx = parent[idx][d];
                    }
                    d--;
                }
                return depth;
            };
            // least common ancestor
            auto get_lca = [&] (int u, int v) {
                int d1 = get_depth(u);
                int d2 = get_depth(v);
                // dbg(mp(d1,d2));

                if (d1 < d2) {
                    swap(u, v);
                }
                LCA lca;
                int t = abs(d1 - d2);
                if (t>0) {
                    t--;
                    rep(i,0,sz(parent[0])) {
                        if (t & (1<<i)) u = parent[u][i];
                    }
                    lca.son1 = nth_son[u];
                    u = parent[u][0];
                }
                if (u == v) {
                    lca.node = u;
                    return lca;
                }

                int d = sz(parent[0]) - 1;
                // dbg(d);
                // dbg(mp(u,v))
                while(d >= 0) {
                    // dbg(mp(parent[u][d], parent[v][d]));
                    if (parent[u][d] != parent[v][d]) {
                        u = parent[u][d];
                        v = parent[v][d];
                    }
                    // dbg(d);
                    // dbg(mp(u,v));
                    d--;
                }
                lca.son1 = nth_son[u];
                lca.son2 = nth_son[v];
                lca.node = parent[u][0];
                return lca;
            };
            
            // O(mlogn)
            vector<vi> node_to_even_edges(n);
            vector<vector<pii>> node_to_direct_sons(n);
            rep(i,0,sz(even_edges)) {
                // dbg(mp(even_edges[i].u, even_edges[i].v));
                LCA lca  = get_lca(even_edges[i].u, even_edges[i].v);
                // dbg(lca);
                node_to_even_edges[lca.node].emplace_back(i);
                node_to_direct_sons[lca.node].emplace_back(mp(lca.son1, lca.son2));
            }
            
            // O(m*2^k)
            vector<vi> dp(n, vi(1<<max_edge_num, -1));
            vector<vi> cache(n, vi(n, -1));
            rep(i,0,n) cache[i][i] = 0;
            rep(u,0,n) {
                for(int v : tree_edges[u]) {
                    cache[u][v] = cache[v][u] = 0;
                }
            }
            function<int(int,int)> get_most_cost = [&] (int node, int mask) {
                // dbg(mp(node, mask));
                if (dp[node][mask] != -1) return dp[node][mask];
                int cost = 0;
                rep(i,0,sz(tree_edges[node])) {
                    if ((1<<i) & mask) continue;
                    if (tree_edges[node][i] == parent[node][0]) continue;
                    cost += get_most_cost(tree_edges[node][i], 0);
                }
                dp[node][mask] = max(dp[node][mask], cost);
                if (node == 0 && mask == 0) {
                    dbg("+++++++++");
                    dbg(cost);
                }

                rep(idx,0,sz(node_to_even_edges[node])) {
                    int i = node_to_even_edges[node][idx];
                    if (node_to_direct_sons[node][idx].first != -1 
                        && (mask & (1<<node_to_direct_sons[node][idx].first))) continue;
                    if (node_to_direct_sons[node][idx].second != -1 
                        && (mask & (1<<node_to_direct_sons[node][idx].second))) continue;

                    cost = even_edges[i].cost;
                    if (node == 0 && mask == 0) {
                        dbg("---------");
                        dbg(cost);
                    }
                    int u = even_edges[i].u, v= even_edges[i].v;
                    if (u != node) cost += get_most_cost(u, 0);
                    if (node == 0 && mask == 0) dbg(cost);
                    if (v != node) cost += get_most_cost(v, 0);
                    if (node == 0 && mask == 0) dbg(cost);

                    vi nodes, subtree_cost;
                    while (true) {
                        if (cache[node][u] != -1) {
                            if (sz(nodes) > 0) {
                                cache[node][nodes.back()] = subtree_cost.back() + cache[node][u];
                                per(i,0,sz(nodes)-1) {
                                    cache[node][nodes[i]] = subtree_cost[i] + cache[node][nodes[i+1]];
                                }
                            }
                            break;
                        }
                        int p = parent[u][0];
                        nodes.emplace_back(u);
                        subtree_cost.emplace_back(get_most_cost(p, (1<<nth_son[u])));
                        u = p;
                    }
                    cost += cache[node][even_edges[i].u];
                    if (node == 0 && mask == 0) {
                        dbg(subtree_cost);
                        dbg(cost);
                    }

                    nodes.clear(), subtree_cost.clear();
                    while (true) {
                        if (cache[node][v] != -1) {
                            if (sz(nodes) > 0) {
                                cache[node][nodes.back()] = subtree_cost.back() + cache[node][v];
                                per(i,0,sz(nodes)-1) {
                                    cache[node][nodes[i]] = subtree_cost[i] + cache[node][nodes[i+1]];
                                }
                            }
                            break;
                        }
                        int p = parent[v][0];
                        nodes.emplace_back(v);
                        subtree_cost.emplace_back(get_most_cost(p, (1<<nth_son[v])));
                        v = p;
                    }
                    cost += cache[node][even_edges[i].v];
                    if (node == 0 && mask == 0) {
                        dbg(subtree_cost);
                        dbg(cost);
                    }

                    int mask2 = mask;
                    if (node_to_direct_sons[node][idx].first != -1)
                        mask2 |= (1<<node_to_direct_sons[node][idx].first);
                    if (node_to_direct_sons[node][idx].second != -1)
                        mask2 |= (1<<node_to_direct_sons[node][idx].second);
                    if (node == 0 && mask == 0) dbg(mask2);
                    cost += get_most_cost(node, mask2);
                    if (node == 0 && mask == 0) dbg(cost);
                    dp[node][mask] = max(dp[node][mask], cost);
                }

                // dbg(mp(node, mask));
                // dbg(dp[node][mask]);
                return dp[node][mask];
            };

            cout << total_cost - get_most_cost(0, 0) << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
#if USACO
    set_io("time");
#else
    set_io("input");
#endif
    Solution().Solve();

    return 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