oj.uz

Submission #532675

# Submission time Handle Problem Language Result Execution time Memory
532675 2022-03-03T15:23:06 Z Alex_tz307 Training (IOI07_training) C++17
100 / 100
 9 ms 720 KB 
#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);
    }
  }
  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);
    }
    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 (w == 0 || (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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 392 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 464 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 3 ms 464 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 5 ms 720 KB Output is correct
3 Correct 3 ms 644 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 9 ms 720 KB Output is correct
4 Correct 2 ms 572 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 6 ms 668 KB Output is correct
3 Correct 4 ms 720 KB Output is correct
4 Correct 4 ms 660 KB Output is correct