Submission #915330

#	Time	Username	Problem	Language	Result	Execution time	Memory
915330		RedGrey1993	Training (IOI07_training)	C++17	100 / 100	21 ms	9016 KiB

training

#include <bits/stdc++.h>

using namespace std;

template <typename T1, typename T2>
istream &operator>>(istream &is, 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:
  // static unsigned int MOD;
  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

// template<typename T>
class Tree { // 下标从0开始
  struct LCA {
    int node;
    int son1 = -1, son2 = -1;
    int dist = 0;
    friend ostream &operator<<(ostream &os, const LCA &r) {
      return os << r.node << "(" << r.son1 << ", " << r.son2 << ")";
    }
  };
 public:
  Tree(int node_num, int root) {
    edges.resize(node_num);
    size.resize(node_num);
    weight.resize(node_num);
    nth_son.resize(node_num);
    centroid[0].resize(node_num, -1);
    centroid[1].resize(node_num, -1);
    this->root = root;

    int bit_num = 1;
    while ((1 << bit_num) < node_num) bit_num++;
    parent.resize(node_num, vi(bit_num));
  }
  void AddEdge(int u, int v) {
    edges[u].emplace_back(v);
    edges[v].emplace_back(u);
  }
  void Dfs() {
    function<void(int, int)> dfs = [&](int u, int p) {
      size[u] = 1;
      for (int i = 0; i < int(edges[u].size()); ++i) {
        int v = edges[u][i];
        if (v != p) {
          parent[v][0] = u;
          nth_son[v] = i;
          dfs(v, u);
          size[u] += size[v];
          weight[u] = max(weight[u], size[v]);
        }
      }

      centroid[0][u] = u;
      for (int v : edges[u]) {
        if (v == p) continue;
        int cen = centroid[0][v];
        while (cen != u) {
          if (max(weight[cen], size[u] - size[cen]) <= size[u] / 2) {
            centroid[0][u] = cen;
            int fa_cen = parent[cen][0];
            if (max(weight[fa_cen], size[u] - size[fa_cen]) <= size[u] / 2)
              centroid[1][u] = fa_cen;
            break;
          }
          else {
            cen = parent[cen][0];
          }
        }
      }
    };
    parent[root][0] = -1;
    nth_son[root] = -1;
    dfs(root, -1);
    // O(nlogn)
    for (int d = 1; d < int(parent[0].size()); ++d) {
      for (int u = 0; u < int(parent.size()); ++u) {
        if (parent[u][d - 1] == -1)
          parent[u][d] = -1;
        else
          parent[u][d] = parent[parent[u][d - 1]][d - 1];
      }
    }
  }

  int GetDepth(int idx) {
    int depth = 0;
    int d = sz(parent[0]) - 1;
    while (idx != root) {
      if (parent[idx][d] != -1) {
        depth |= (1 << d);
        idx = parent[idx][d];
      }
      d--;
    }
    return depth;
  };

  // least common ancestor
  LCA GetLca(int u, int v) {
    int d1 = GetDepth(u);
    int d2 = GetDepth(v);

    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;
      lca.dist = abs(d1 - d2);
      return lca;
    }

    int d = sz(parent[0]) - 1;
    while (d >= 0) {
      if (parent[u][d] != parent[v][d]) {
        u = parent[u][d];
        v = parent[v][d];
      }
      d--;
    }
    lca.son1 = nth_son[u];
    lca.son2 = nth_son[v];
    lca.node = parent[u][0];
    lca.dist = d1 + d2 - 2 * GetDepth(lca.node);
    return lca;
  }

  const vector<int>& GetCentroid(int idx) {
    return centroid[idx];
  }

  const vector<vector<int>>& GetEdges() {
    return edges;
  }

  const vector<vector<int>>& GetParent() {
    return parent;
  }

  const vector<int>& GetNthSon() {
    return nth_son;
  }

 private:
  // nth_son[i] indicates which son of the father is i.
  // nth_son[i] 表示i是父节点的第几个子节点
  vector<int> nth_son;
  vector<vector<int>> edges;
  vector<vector<int>> parent;
  vector<int> size; // size[i]表示以节点i为根的子树（整颗数以root为根）的节点个数，包括i节点本身
  vector<int> weight;  // weight[i]表示节点i的所有子树的节点数的最大值，包括向上的子树
  vector<int> centroid[2]; //centroid[i]表示以节点i为根的子树（整颗数以root为根）的重心，重心最多有两个（质心）
  int root = 0;
};

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;
    }
  };

 public:
  void Solve() {
    int n, m;
    // n<=1000, m<=5000
    while (cin >> n >> m) {
      int total_cost = 0;

      vi degree(n);
      Tree tree(n, 0);
      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.AddEdge(u, v);
        } else {
          edges.emplace_back(Edge{u, v, c});
          total_cost += c;
        }
      }

      tree.Dfs();

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

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

      // 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));
        auto lca = tree.GetLca(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_degree, -1));
      vector<vi> cache(n, vi(n, -1));
      const vector<vector<int>>& tree_edges = tree.GetEdges();
      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;
        }
      }
      const vector<vi>& parent = tree.GetParent();
      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);

        const vector<int>& nth_son = tree.GetNthSon();
        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;
          int u = even_edges[i].u, v = even_edges[i].v;
          if (u != node) cost += get_most_cost(u, 0);
          if (v != node) cost += get_most_cost(v, 0);

          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];

          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];

          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);
          cost += get_most_cost(node, mask2);
          dp[node][mask] = max(dp[node][mask], cost);
        }

        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