oj.uz

Submission #239735

# Submission time Handle Problem Language Result Execution time Memory
239735 2020-06-17T08:25:38 Z neihcr7j Beads and wires (APIO14_beads) C++14
0 / 100
 9 ms 5120 KB 
#include<bits/stdc++.h>

#define oo 1000000000
#define maxn 200005

using namespace std;
typedef long long ll;

int n;

vector < pair < int, int > > g[maxn];

int dp[maxn][4];

void dfs(int u, int du) {
  dp[u][0] = dp[u][1] = 0;
  dp[u][2] = dp[u][3] = -oo;

  for (auto i : g[u]) {
    int v = i.first, w = i.second;
    if (du == v) continue;

    dfs(v, u);

    if (u == 8) cerr << v << '\n';

    int ret = max(dp[v][0], dp[v][1]);

    int a = max(dp[u][0] + max(dp[v][1], dp[v][2] + w), dp[u][1] + dp[v][3] + w);
    //if (u == 1) cerr << v << '\n';
    a = max(a, max(dp[u][2] + ret, dp[u][3] + dp[v][1]) + w);

    int b = dp[u][1] + max(dp[v][1], dp[v][2] + w);
    int c = max(dp[u][2] + max(dp[v][2] + w, ret), dp[u][1] + dp[v][1] + w);
    int d = max(dp[u][3] + max(dp[v][2] + w, ret), dp[u][1] + ret + w);

    dp[u][0] = a;
    dp[u][1] = b;
    dp[u][2] = c;
    dp[u][3] = d;

    //if (u == 8) cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
  }
}

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n;

  for (int i = 1; i < n; ++i) {
    int u, v, c;
    cin >> u >> v >> c;

    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }

  int root = 1;
  dfs(root, root);

  //cerr << dp[8][1] << '\n';

  cout << max(dp[root][0], dp[root][1]);

  return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -