Submission #987734

#	Time	Username	Problem	Language	Result	Execution time	Memory
987734		MilosMilutinovic	Training (IOI07_training)	C++14	100 / 100	14 ms	1116 KiB

training

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<array<int, 3>> e;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u; --v;
    if (w == 0) {
      g[u].push_back(v);
      g[v].push_back(u);
    } else {
      e.push_back({u, v, w});
    }
  }
  const int L = 20;
  vector<vector<int>> jump(n, vector<int>(L));
  vector<int> dep(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    jump[v][0] = pv;
    for (int i = 1; i < L; i++) {
      jump[v][i] = jump[jump[v][i - 1]][i - 1];
    }
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      dep[u] = dep[v] + 1;
      Dfs(u, v);
    }
  };
  auto LCA = [&](int u, int v) {
    if (dep[u] > dep[v]) {
      swap(u, v);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[jump[v][i]] >= dep[u]) {
        v = jump[v][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int i = L - 1; i >= 0; i--) {
      if (jump[u][i] != jump[v][i]) {
        u = jump[u][i];
        v = jump[v][i];
      }
    }
    return jump[u][0];
  };
  auto GetDist = [&](int u, int v) {
    return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
  };
  Dfs(0, 0);
  long long s = 0;
  vector<vector<array<int, 3>>> qs(n);
  for (auto &p : e) {
    s += p[2];
    if (GetDist(p[0], p[1]) % 2 == 1) {
      continue;
    }
    qs[LCA(p[0], p[1])].push_back(p);
  }
  vector<vector<long long>> dp(n);
  vector<int> idx(n);
  vector<int> deg(n);
  Dfs = [&](int v, int pv) {
    long long sum_ch = 0;
    vector<int> ch;
    for (int i = 0; i < (int) g[v].size(); i++) {
      int u = g[v][i];
      if (u == pv) {
        continue;
      }
      deg[v] += 1;
      Dfs(u, v);
      sum_ch += *max_element(dp[u].begin(), dp[u].end());
      idx[u] = (int) ch.size();
      ch.push_back(u);
    }
    dp[v].resize(1 << deg[v]);
    fill(dp[v].begin(), dp[v].end(), 0LL);
    for (int mask = 0; mask < (1 << deg[v]); mask++) {
      for (int i = 0; i < deg[v]; i++) {
        if (mask >> i & 1) {
          dp[v][mask] += *max_element(dp[ch[i]].begin(), dp[ch[i]].end());
        }
      }
    }
    vector<pair<int, long long>> opt;
    for (auto &p : qs[v]) {
      int a = p[0];
      int b = p[1];
      int c = p[2];
      long long ft = c;
      int mask = 0;
      {
        int x = a;
        int prv = -1;
        while (x != v) {
          int cmask = (1 << deg[x]) - 1;
          if (prv != -1) {
            cmask ^= (1 << idx[prv]);
          }
          ft += dp[x][cmask];
          prv = x;
          x = jump[x][0];
        }
        if (prv != -1) {
          mask ^= (1 << idx[prv]);
        }
      }
      {
        int x = b;
        int prv = -1;
        while (x != v) {
          int cmask = (1 << deg[x]) - 1;
          if (prv != -1) {
            cmask ^= (1 << idx[prv]);
          }
          ft += dp[x][cmask];
          prv = x;
          x = jump[x][0];
        }
        if (prv != -1) {
          mask ^= (1 << idx[prv]);
        }
      }
      opt.push_back({mask, ft});
    }
    for (auto &p : opt) {
      auto new_dp = dp[v];
      for (int mask = 0; mask < (1 << deg[v]); mask++) {
        if (mask & p.first) {
          continue;
        }
        new_dp[mask | p.first] = max(new_dp[mask | p.first], dp[v][mask] + p.second);
      }
      swap(dp[v], new_dp);
    }
  };
  Dfs(0, 0);
  cout << s - dp[0].back() << '\n';
  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