Submission #955832

#	Time	Username	Problem	Language	Result	Execution time	Memory
955832		Yang8on	Power Plant (JOI20_power)	C++14	100 / 100	121 ms	28844 KiB

power

#include <bits/stdc++.h>
#define gsn "Power Plant"
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r) (rng);
}

const int maxn = 200005;

int n, ans;
int dp[maxn];
string s;
vector<int> o[maxn];

void dfs(int u, int par)
{
    int sum = 0, mx = 0;
    for(int v : o[u])
    {
        if(v == par) continue;
        dfs(v, u);

        sum += dp[v], mx = max(mx, dp[v]);
    }

    ans = max({ ans, sum - (s[u] == '1'), mx + (s[u] == '1') });
    dp[u] = max({ (int)(s[u] == '1'), sum - (s[u] == '1'), mx - (s[u] == '1') });
}

void solve()
{
    cin >> n;
    fi(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;

        o[u].push_back(v);
        o[v].push_back(u);
    }

    cin >> s, s = ' ' + s;

    dfs(1, -1);

    cout << ans ;
}


int main()
{
    if(fopen(gsn".inp", "r"))
    {
        freopen(gsn".inp", "r", stdin);
        freopen(gsn".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }




    /// ------------------check time!-----------------///
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(gsn".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
power.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(gsn".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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