oj.uz

Submission #660861

# Submission time Handle Problem Language Result Execution time Memory
660861 2022-11-23T10:58:12 Z Danilo21 Power Plant (JOI20_power) C++14
0 / 100
 14 ms 23892 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
int n, m, gen[mxN], dp[mxN];
vector<int> g[mxN];

int dfs(int s = 0, int p = -1){

    int sum = 0, mx = 0, ans = 0;
    for (int u : g[s]){
        if (u^p){
            smax(ans, dfs(u, s));
            sum += dp[u];
            smax(mx, dp[u]);
        }
    }
    dp[s] = max(sum - gen[s], gen[s]);
    return max(ans, max(mx + gen[s], sum));
}

void Solve(){

    cin >> n;
    for (int i = 1; i < n; i++){
        ri(u); ri(v);
        u--; v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    rs(s);
    for (int i = 0; i < n; i++)
        gen[i] = (int)(s[i] - '0');
    cout << dfs() << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23704 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 13 ms 23816 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Incorrect 14 ms 23708 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23704 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 13 ms 23816 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Incorrect 14 ms 23708 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23704 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 13 ms 23816 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Incorrect 14 ms 23708 KB Output isn't correct
13 Halted 0 ms 0 KB -