oj.uz

Submission #623215

# Submission time Handle Problem Language Result Execution time Memory
623215 2022-08-05T10:35:58 Z K4YAN Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4948 KB 
//Be Name Khoda

#include<bits/stdc++.h>
//pragma shayad niaz she

using namespace std;

typedef long long ll;
typedef long double ld;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll mxn = 2e5 + 16;
ll n, m, t, q, w, ans;
ll dp[mxn], subt[mxn];
vector<ll> adj[mxn];
bool mark[mxn];
string s;

void input() {

    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> q >> w;
        adj[q].push_back(w);
        adj[w].push_back(q);
    } cin >> s;
    s = '0' + s;

}

void DFS(int v) {
    mark[v] = 1;
    ll cnt = 0, sum = 0, idk = 0;
    if(s[v] == '1') dp[v] = 1, subt[v] = 1;
    for(auto u : adj[v]) {
        if(!mark[u]) {
            DFS(u);
            if(subt[u] > 0) {
                subt[v] += subt[u];
                cnt++, sum += dp[u];
                idk = max(idk, dp[u]);
            }
        }
    }
    if(s[v] == '1') {
        ans = max(ans, idk + 1);
    }
    if(cnt > 1 && s[v] == '1') {
        sum--;
    } 
    dp[v] = max(dp[v], sum); 
    return;
}

void solve() {

    ll cnt = 0;
    for(auto u : s) {
        if(u == '1') cnt++;
    }
    if(cnt < 3) {
        cout << cnt << "\n";
        return;
    }
    DFS(1);
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 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 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Incorrect 3 ms 4948 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 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 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 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Incorrect 3 ms 4948 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 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 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 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Incorrect 3 ms 4948 KB Output isn't correct
13 Halted 0 ms 0 KB -