Submission #1250716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250716		kunzaZa183	Training (IOI07_training)	C++20	100 / 100	19 ms	14404 KiB

training

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<array<int, 3>> vai3;
  int tot = 0;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    if (c == 0) {
      adj[a].push_back(b), adj[b].push_back(a);
    } else {
      tot += c;
      vai3.push_back({a, b, c});
    }
  }

  vector<int> dep(n);
  vector<int> parvi(n);
  vector<int> which(n);
  int curd = 0;
  function<void(int, int, int)> fvii = [&](int cur, int par, int in) {
    dep[cur] = curd;
    which[cur] = in;
    parvi[cur] = par;
    for (int i = 0; i < adj[cur].size(); i++)
      if (adj[cur][i] == par) {
        swap(adj[cur][i], adj[cur].back());
      }
    if (par != -1)
      adj[cur].pop_back();

    for (int i = 0; i < adj[cur].size(); i++) {
      curd++;
      fvii(adj[cur][i], cur, i);
      curd--;
    }
  };
  fvii(0, -1, -1);

  vector<array<int, 3>> vai32;
  for (auto [a, b, c] : vai3) {
    if (dep[a] % 2 == dep[b] % 2)
      vai32.push_back({a, b, c});
  }

  vai3.swap(vai32);

  vector<vector<int>> lca(n);
  vector<vector<pair<int, int>>> vvpii;
  for (int i = 0; i < vai3.size(); i++) {
    auto [a, b, c] = vai3[i];
    vvpii.emplace_back();
    if (dep[a] > dep[b])
      swap(a, b);

    while (dep[a] < dep[b]) {
      if (parvi[b] == a) {
        vvpii.back().emplace_back(parvi[b], 1 << which[b]);
      } else
        vvpii.back().emplace_back(parvi[b], ((1 << adj[parvi[b]].size()) - 1) ^
                                                (1 << which[b]));
      b = parvi[b];
    }

    while (a != b) {
      if (parvi[a] == parvi[b]) {
        vvpii.back().emplace_back(parvi[a], (1 << which[b]) ^ (1 << which[a]));
      } else {
        vvpii.back().emplace_back(parvi[a], ((1 << adj[parvi[a]].size()) - 1) ^
                                                (1 << which[a]));
        vvpii.back().emplace_back(parvi[b], ((1 << adj[parvi[b]].size()) - 1) ^
                                                (1 << which[b]));
      }
      a = parvi[a], b = parvi[b];
    }

    lca[a].push_back(i);
  }

  vector<vector<int>> dp(n);
  function<void(int)> dfs2 = [&](int cur) {
    for (auto a : adj[cur]) {
      dfs2(a);
    }

    dp[cur].resize(1 << adj[cur].size());
    vector<int> lcaval(lca[cur].size());

    for (int i = 0; i < lca[cur].size(); i++) {
      int in = lca[cur][i];

      lcaval[i] = vai3[in][2];
      if (vai3[in][0] != vvpii[in].back().first)
        lcaval[i] += dp[vai3[in][0]].back();
      if (vai3[in][1] != vvpii[in].back().first)
        lcaval[i] += dp[vai3[in][1]].back();

      for (int j = 0; j + 1 < vvpii[in].size(); j++) {
        lcaval[i] += dp[vvpii[in][j].first][vvpii[in][j].second];
      }
    }

    for (int i = 0; i < dp[cur].size(); i++) {
      for (int j = 0; j < lca[cur].size(); j++) {
        int in = lca[cur][j];
        if ((i & vvpii[in].back().second) == vvpii[in].back().second)
          dp[cur][i] =
              max(dp[cur][i], dp[cur][i ^ vvpii[in].back().second] + lcaval[j]);
      }

      int val = 0;
      for (int j = 0; j < adj[cur].size(); j++) {
        if ((1 << j) & i)
          val += dp[adj[cur][j]].back();
      }
      dp[cur][i] = max(dp[cur][i], val);
    }
  };
  dfs2(0);

  cout << tot - dp[0].back() << "\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