oj.uz

답안 #766775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766775 2023-06-26T07:15:35 Z ParsaS Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4948 KB 
// 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]) {
        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
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -