답안 #766779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766779	2023-06-26T07:18:49 Z	ParsaS	Power Plant (JOI20_power)	C++17	6 / 100	3 ms	5204 KB

power

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5;
int n;
vector<int> adj[N];
string s;
int dp[N], up[N], par[N];

void dfs(int v, int p) {
    par[v] = p;
    int sum = 0;
    for (auto u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            sum += dp[u];
        }
    }
    dp[v] = max(0, sum - 1);
    if (s[v] == '0')
        dp[v] = sum;
    else
        dp[v] = max(dp[v], 1);
}
void dfs2(int v, int p) {
    int sum = 0;
    for (auto u : adj[v]) {
        if (u != p)
            sum += dp[u];
    }
    for (auto u : adj[v]) {
        if (u != p) {
            up[u] = max(0, up[p] + sum - dp[u] - 1);
            if (s[v] == '0')
                up[u] = up[p] + sum - dp[u];
            else
                up[u] = max(up[u], 1);
            dfs2(u, v);
        }
    } 
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int v, u; cin >> v >> u;
        v--, u--;
        adj[v].pb(u), adj[u].pb(v);
    }
    cin >> s;
    dfs(0, 0);
    dfs2(0, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            ans = max(ans, up[i] + 1);
            for (auto u : adj[i])
                if (u != par[i])
                    ans = max(ans, dp[u] + 1);
        }
    }
    cout << ans << '\n';
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	2 ms	4908 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	5004 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	4948 KB	Output is correct
12	Correct	2 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	2 ms	4948 KB	Output is correct
17	Correct	2 ms	4948 KB	Output is correct
18	Correct	2 ms	4948 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct
21	Correct	2 ms	4948 KB	Output is correct

Subtask #2

0.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	2 ms	4908 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	5004 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	4948 KB	Output is correct
12	Correct	2 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	2 ms	4948 KB	Output is correct
17	Correct	2 ms	4948 KB	Output is correct
18	Correct	2 ms	4948 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct
21	Correct	2 ms	4948 KB	Output is correct
22	Correct	3 ms	5076 KB	Output is correct
23	Correct	3 ms	5076 KB	Output is correct
24	Correct	3 ms	5076 KB	Output is correct
25	Correct	3 ms	5076 KB	Output is correct
26	Correct	3 ms	5076 KB	Output is correct
27	Correct	3 ms	5076 KB	Output is correct
28	Correct	3 ms	5076 KB	Output is correct
29	Correct	3 ms	5204 KB	Output is correct
30	Correct	3 ms	5188 KB	Output is correct
31	Correct	3 ms	5076 KB	Output is correct
32	Correct	3 ms	5076 KB	Output is correct
33	Incorrect	3 ms	5076 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	2 ms	4908 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	5004 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	4948 KB	Output is correct
12	Correct	2 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	2 ms	4948 KB	Output is correct
17	Correct	2 ms	4948 KB	Output is correct
18	Correct	2 ms	4948 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	2 ms	4948 KB	Output is correct
21	Correct	2 ms	4948 KB	Output is correct
22	Correct	3 ms	5076 KB	Output is correct
23	Correct	3 ms	5076 KB	Output is correct
24	Correct	3 ms	5076 KB	Output is correct
25	Correct	3 ms	5076 KB	Output is correct
26	Correct	3 ms	5076 KB	Output is correct
27	Correct	3 ms	5076 KB	Output is correct
28	Correct	3 ms	5076 KB	Output is correct
29	Correct	3 ms	5204 KB	Output is correct
30	Correct	3 ms	5188 KB	Output is correct
31	Correct	3 ms	5076 KB	Output is correct
32	Correct	3 ms	5076 KB	Output is correct
33	Incorrect	3 ms	5076 KB	Output isn't correct
34	Halted	0 ms	0 KB	-