Submission #315799

#	Time	Username	Problem	Language	Result	Execution time	Memory
315799		12tqian	Power Plant (JOI20_power)	C++17	100 / 100	439 ms	31680 KiB

power

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define eb emplace_back
#define pb push_back
#define sz(x) (int) (x).size()
#define mp make_pair

#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    f0r(i, n-1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    string s;
    cin >> s;
    vector<int> dp(n);
    int ans = 0;
    function<void(int, int)> dfs = [&](int src, int par) {
        for (int nxt: adj[src]) {
            if (nxt == par) continue;
            dfs(nxt, src);
        }
        if (s[src] == '0') {
            int res = 0;
            for (int nxt: adj[src]) {
                if (nxt == par) continue;
                res += max(0, dp[nxt]);
            }
            ckmax(dp[src], res);
            // actually updating ans, assume nothing is actually above

        } else {
            // no paths
            dp[src] = 1;
            // at least one path
            // under the assumption something's above
            int res = -1;
            for (int nxt: adj[src]) {
                res += max(0, dp[nxt]);
            }
            ckmax(dp[src], res);
            // the node becomes negative
            ckmax(ans, res);
            // the node does not become negative
            res = 0;
            for (int nxt: adj[src]) {
                if (nxt == par) continue;
                ckmax(res, dp[nxt]);
            }
            ckmax(ans, res + 1);
        }
        ckmax(ans, dp[src]);
    };
    dfs(0, -1);
    cout << ans << '\n';
    return 0;
}

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