Submission #1212682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212682		rxlfd314	Training (IOI07_training)	C++17	100 / 100	14 ms	840 KiB

training

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct chash {
  const uint64_t C = uint64_t(4e18 * acos(0)) + 71;
  const uint64_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  ll operator()(const uint64_t x) const {
    return __builtin_bswap64((x ^ RANDOM) * C);
  }
};

template <class T> T chmax(T &a, const T b) {
  return a = max(a, b);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N, M;
  cin >> N >> M;
  vt<vt<int>> adj(N);
  vt<ari3> edges;
  int tot = 0;
  FOR(_, 1, M) {
    int a, b, c;
    cin >> a >> b >> c, a--, b--;
    tot += c;
    if (c)
      edges.push_back({a, b, c});
    else {
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
  }
  vt<int> depth(N), parent(N);
  const auto dfs_depth = [&](auto &&self, const int i, const int p) -> void {
    parent[i] = p;
    int bad = -1;
    FOR(j, 0, size(adj[i]) - 1) {
      if (adj[i][j] == p)
        bad = j;
      else {
        depth[adj[i][j]] = depth[i] + 1;
        self(self, adj[i][j], i);
      }
    }
    if (bad >= 0)
      adj[i].erase(adj[i].begin() + bad);
  };
  dfs_depth(dfs_depth, 0, -1);
  const auto lca = [&](int a, int b) {
    for (; depth[a] > depth[b]; a = parent[a]);
    for (; depth[b] > depth[a]; b = parent[b]);
    for (; a != b; a = parent[a], b = parent[b]);
    return a;
  };
  vt<vt<ari3>> sweep(N);
  for (const auto &[a, b, c] : edges)
    if (depth[a] + depth[b] + 1 & 1)
      sweep[lca(a, b)].push_back({a, b, c});
  vt<vt<int>> dp(N);
  vt<int> max_dp(N);
  vt<unordered_map<int, int, chash>> inds(N);
  const auto dfs = [&](auto &&self, const int i, const int p) -> void {
    dp[i].assign(1 << size(adj[i]), 0);
    FOR(j, 0, size(adj[i]) - 1) {
      inds[i][adj[i][j]] = j;
      self(self, adj[i][j], i);
    }
    for (auto [a, b, c] : sweep[i]) {
      int v = c + (a != i) * max_dp[a];
      for (; a != i && parent[a] != i; a = parent[a])
        v += dp[parent[a]][size(dp[parent[a]]) - 1 - (1 << inds[parent[a]][a])];
      v += (b != i) * max_dp[b];
      for (; b != i && parent[b] != i; b = parent[b])
        v += dp[parent[b]][size(dp[parent[b]]) - 1 - (1 << inds[parent[b]][b])];
      chmax(dp[i][(a != i ? 1 << inds[i][a] : 0) | (b != i ? 1 << inds[i][b] : 0)], v);
    }
    FOR(j, 1, size(dp[i]) - 1) {
      int v = 0;
      FOR(k, 0, size(adj[i]) - 1)
        if (j >> k & 1)
          v += max_dp[adj[i][k]];
      chmax(dp[i][j], v);
    }     
    FOR(j, 1, size(dp[i]) - 1)
      for (int k = j; k; k = (k - 1) & j)
        chmax(max_dp[i], chmax(dp[i][j], dp[i][k] + dp[i][j ^ k]));
  };
  dfs(dfs, 0, -1);
  
  cout << tot - *max_element(all(max_dp)) << '\n';
}

• 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