Submission #1159162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159162		Der_Vlapos	Power Plant (JOI20_power)	C++20	0 / 100	0 ms	328 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()

// #define int ll

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

int dp1[1003][1003];
int dp2[1003][1003];

struct test
{
    vector<vector<int>> tree;
    vector<vector<int>> dp;
    vector<int> isG;

    void solve(int v, int pr = -1)
    {
        for (auto tov : tree[v])
            if (tov != pr)
                solve(tov, v);

        int sum = 0;
        dp[v][2] = 0;
        int mx = 0;
        for (auto tov : tree[v])
        {
            sum += dp[tov][1];
            dp[v][2] = max(dp[v][2], dp[tov][2]);
            mx = max(mx, dp[tov][1]);
        }
        dp[v][1] = max(isG[v], sum - isG[v]);
        dp[v][2] = max({dp[v][2], sum, mx + isG[v]});
        dp[v][2] = max(dp[v][2], dp[v][1]);
        // cout << v << " " << dp[v][1] << " | " << dp[v][2] << "\n";
    }

    void solve()
    {
        int n;
        cin >> n;
        tree.resize(n);
        dp.resize(n, vector<int>(3));
        isG.resize(n);
        for (int i = 1; i < n; ++i)
        {
            int v, tov;
            cin >> v >> tov;
            --v, --tov;
            tree[v].pb(tov);
            tree[tov].pb(v);
        }

        for (int i = 0; i < n; ++i)
        {
            char x;
            cin >> x;
            isG[i] = x == '1';
        }

        solve(0);

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

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

power.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main()
      | ^~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53