Submission #532670

#	Time	Username	Problem	Language	Result	Execution time	Memory
532670		Alex_tz307	Training (IOI07_training)	C++17	30 / 100	5 ms	588 KiB

training

#include <bits/stdc++.h>

using namespace std;

// Formulare: Adauga muchii la arbore astfel incat suma costurilor sa fie maxima si
// graful obtinut sa nu aiba cicluri pare
// Consider muchiile (u, v) care nu fac parte din arbore
// Observatia 1: O muchie pe care o prelungesc cu drumul u-v din arbore nu este adaugata
// in solutie daca formeaza un ciclu par
// Observatia 2: O muchie din arbore nu poate fi obtinuta in mai multe cicluri impare
// pentru ca prin eliminarea acesteia s-ar obtine un ciclu par
// Observatia 3: Imi este de ajuns sa ma asigur dupa ce adaug un ciclu impar ca nu
// mai folosesc muchiile sale din arbore in alte cicluri.
// Proof 3: Un ciclu par trebuie sa contina cel putin o muchie din afara arborelui.
// Daca e exact una e bine pentru ca am stabilit la observatia 1 ce muchii aleg,
// daca sunt cel putin 2, observatiile 2 si 3 rezolva problema.
// dp[nod][mask] =def= costul maxim daca consider subarborele cu radacina in nod si mask
// imi zice muchiile (nod, son) "eliminate"
// => dp[1][0]

const int kN = 1e3;
const int kM = 5e3;
int timer, tin[1 + kN], tout[1 + kN], dep[1 + kN];
vector<int> g[1 + kN], dp[1 + kN];
pair<int, int> par[1 + kN];
vector<tuple<int, int, int>> paths[1 + kN];

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void dfs1(int u) {
  tin[u] = ++timer;
  int cnt = 0;
  for (int v : g[u]) {
    if (v != par[u].first) {
      par[v] = {u, 1 << cnt};
      cnt += 1;
      dep[v] = dep[u] + 1;
      dfs1(v);
    }
  }
  dp[u].resize(1 << cnt);
  tout[u] = timer;
}

bool isAncestor(int u, int v) {
  return tin[u] <= tin[v] && tin[v] <= tout[u];
}

void dfs2(int u) {
  for (int v : g[u]) {
    if (v != par[u].first) {
      dfs2(v);
      dp[u][0] += dp[v][0];
    }
  }
  for (auto it : paths[u]) {
    int p, q, w;
    tie(p, q, w) = it;
    pair<int, int> U, V;
    int sum = w;
    for (U = {p, 0}; U.first != u; U = par[U.first]) {
      sum += dp[U.first][U.second];
    }
    for (V = {q, 0}; V.first != u; V = par[V.first]) {
      sum += dp[V.first][V.second];
    }
    for (int mask = dp[u].size() - 1; mask >= 0; --mask) {
      if (!(mask & U.second) && !(mask & V.second)) {
        maxSelf(dp[u][mask], dp[u][mask | U.second | V.second] + sum);
      }
    }
  }
}

void testCase() {
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> edges;
  int sum = 0;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    if (w == 0) {
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    } else {
      edges.emplace_back(u, v, w);
      sum += w;
    }
  }
  dfs1(1);
  for (auto it : edges) {
    int u, v, w;
    tie(u, v, w) = it;
    int lca = v, other = u;
    if (dep[u] < dep[v]) {
      swap(lca, other);
    }
    while (!isAncestor(lca, other)) {
      lca = par[lca].first;
    }
    if ((dep[u] + dep[v] - 2 * dep[lca]) % 2 == 0) {
      paths[lca].emplace_back(u, v, w);
    }
  }
  dfs2(1);
  cout << sum - dp[1][0] << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9