Submission #501642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
501642	2022-01-04T09:06:46 Z	600Mihnea	Training (IOI07_training)	C++17	100 / 100	27 ms	4844 KB

training

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Guy {
  int a;
  int b;
  int cost;
};


const int N = 1000 + 7;
const int INF = (int) 1e18;
const int B = 10;
vector<Guy> offers[N];
int sz[N];
int dp[N][1 << B];
int n;
int m;
vector<int> g[N];
int totalG;
int dep[N];
int parrent[N];

int getLca(int a, int b) {
  while (a != b) {
    assert(a >= 1);
    assert(b >= 1);
    if (dep[a] > dep[b]) {
      a = parrent[a];
    } else {
      b = parrent[b];
    }
  }
  return a;
}

void build(int a, int p = -1) {
  vector<int> relege;
  parrent[a] = p;
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }

    dep[b] = 1 + dep[a];
    relege.push_back(b);
    build(b, a);
  }
  g[a] = relege;
}

int who[N];
int skip[N];

void dfs(int a) {
  for (auto &b : g[a]) {
    dfs(b);
  }
  for (auto &it : offers[a]) {
    vector<int> pathX, pathY;
    int C = it.cost;
    {
      int X = it.a, Y = it.b;
      while (X != a) {
        assert(X >= 1);
        pathX.push_back(X);
        X = parrent[X];
      }
      while (Y != a) {
        assert(Y >= 1);
        pathY.push_back(Y);
        Y = parrent[Y];
      }
      reverse(pathX.begin(), pathX.end());
      reverse(pathY.begin(), pathY.end());
    }
    {
      skip[a] = 0;
      for (auto &it : pathX) skip[it] = 0;
      for (auto &it : pathY) skip[it] = 0;
    }
    if (!pathX.empty()) skip[a] += (1 << who[pathX[0]]);
    if (!pathY.empty()) skip[a] += (1 << who[pathY[0]]);
    for (int j = 0; j + 1 < (int) pathX.size(); j++) skip[pathX[j]] += (1 << who[pathX[j + 1]]);
    for (int j = 0; j + 1 < (int) pathY.size(); j++) skip[pathY[j]] += (1 << who[pathY[j + 1]]);
    int current = C;
    for (auto &it : pathX) current += dp[it][(1 << sz[it]) - 1 - skip[it]];
    for (auto &it : pathY) current += dp[it][(1 << sz[it]) - 1 - skip[it]];
    dp[a][skip[a]] = max(dp[a][skip[a]], current);
  }
  for (int mask = 0; mask < (1 << sz[a]); mask++) {
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
      dp[a][mask] = max(dp[a][mask], dp[a][sub] + dp[a][mask ^ sub]);
    }
    int mx = 0;
    for (int it = 0; it < sz[a]; it++) {
      if (mask & (1 << it)) {
        mx += dp[g[a][it]][(1 << sz[g[a][it]]) - 1];
      }
    }
    dp[a][mask] = max(dp[a][mask], mx);
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 /// freopen ("input", "r", stdin);

  cin >> n >> m;
  vector<Guy> guys;
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (!c) {
      totalG++;
      g[a].push_back(b);
      g[b].push_back(a);
    } else {
      guys.push_back({a, b, c});
    }
  }
  assert(totalG == n - 1);
  build(1);
  for (int i = 1; i <= n; i++) {
    sz[i] = (int) g[i].size();
    for (int j = 0; j < (int) g[i].size(); j++) {
      who[g[i][j]] = j;
    }
  }
  int needToPay = 0, totalSm = 0;
  for (auto &it : guys) {
    int a = it.a;
    int b = it.b;
    int cost = it.cost;
    if (dep[a] % 2 != dep[b] % 2) {
      needToPay += cost;
    } else {
      int lca = getLca(a, b);
      offers[lca].push_back(it);
      totalSm += cost;
    }
  }
  dfs(1);
  cout << needToPay + (totalSm - dp[1][(1 << sz[1]) - 1]) << "\n";
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	1 ms	480 KB	Output is correct
2	Correct	1 ms	588 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4688 KB	Output is correct
2	Correct	12 ms	4728 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	332 KB	Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	752 KB	Output is correct
2	Correct	1 ms	756 KB	Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4676 KB	Output is correct
2	Correct	13 ms	4812 KB	Output is correct
3	Correct	5 ms	4732 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2668 KB	Output is correct
2	Correct	5 ms	2556 KB	Output is correct
3	Correct	24 ms	4772 KB	Output is correct
4	Correct	6 ms	2620 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4736 KB	Output is correct
2	Correct	27 ms	4816 KB	Output is correct
3	Correct	14 ms	4844 KB	Output is correct
4	Correct	7 ms	4812 KB	Output is correct

Submission #501642

Compilation message