oj.uz

답안 #501642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501642 2022-01-04T09:06:46 Z 600Mihnea Training (IOI07_training) C++17
100 / 100
 27 ms 4844 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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