oj.uz

Submission #457554

# Submission time Handle Problem Language Result Execution time Memory
457554 2021-08-07T08:16:56 Z prvocislo Beads and wires (APIO14_beads) C++17
0 / 100
 18 ms 15948 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 2e5 + 5;
const int inf = 2e9 + 5;
vector<vector<int> > dp(maxn, vector<int>(2, -inf));
vector<vector<pair<int, int> > > g(maxn);
void upd(int& a, const int& b)
{
    a = max(a, b);
}
void dfs(int u, int p, int w)
{
    vector<int> dp2(3, -inf);
    dp2[0] = 0;
    for (const pair<int, int>& v : g[u])
    {
        if (v.first == p)
        {
            continue;
        }
        dfs(v.first, u, v.second);
        vector<int> dpnw(3, -inf);
        for (int i = 0; i < 3; i++)
        {
            upd(dpnw[i], dp2[i] + max(dp[v.first][0], dp[v.first][1]));
            if (i != 2)
            {
                upd(dpnw[i + 1], dp2[i] + dp[v.first][0] + v.second);
            }
        }
        dp2 = dpnw;
    }
    upd(dp[u][0], dp2[0]);
    upd(dp[u][0], dp2[2]);
    if (p != -1)
    {
        upd(dp[u][1], dp2[1] + w);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[--a].push_back({ --b, c });
        g[b].push_back({ a, c });
    }
    dfs(0, -1, -1);
    cout << dp[0][0] << "\n";
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15948 KB Output is correct
2 Correct 15 ms 15948 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 15 ms 15948 KB Output is correct
5 Correct 18 ms 15948 KB Output is correct
6 Incorrect 16 ms 15948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15948 KB Output is correct
2 Correct 15 ms 15948 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 15 ms 15948 KB Output is correct
5 Correct 18 ms 15948 KB Output is correct
6 Incorrect 16 ms 15948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15948 KB Output is correct
2 Correct 15 ms 15948 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 15 ms 15948 KB Output is correct
5 Correct 18 ms 15948 KB Output is correct
6 Incorrect 16 ms 15948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15948 KB Output is correct
2 Correct 15 ms 15948 KB Output is correct
3 Correct 15 ms 15948 KB Output is correct
4 Correct 15 ms 15948 KB Output is correct
5 Correct 18 ms 15948 KB Output is correct
6 Incorrect 16 ms 15948 KB Output isn't correct
7 Halted 0 ms 0 KB -