oj.uz

Submission #1069254

# Submission time Handle Problem Language Result Execution time Memory
1069254 2024-08-21T18:13:13 Z sitablechair Power Plant (JOI20_power) C++17
0 / 100
 1 ms 6584 KB 
#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+9;

int fc[N],f[N];
vector<int> g[N];
int c[N];
int n,ans=0;
void dfs(int u,int p=0) {
    f[u]=c[u];
    for(auto v: g[u]) if (v!=p) {
        dfs(v,u);
        fc[u]+=f[v];
    }
    f[u]=max(f[u],fc[u]-c[u]);
    if (u==1) f[u]=max(f[u],fc[u]+c[u]);
}
void dfs1(int u,int p=0) {
    int tmp1=fc[p],tmp2=f[p],tmp3=f[u];
    if (u!=1) {
        if (c[u] && c[u]<fc[u]+c[u]) f[u]--;
        fc[p]-=f[u];
        f[p]=max(c[p],fc[p]-c[p]);
        fc[u]+=f[p];
        f[u]=max(c[u],fc[u]-c[u]);
        if (c[u]) {
            ans=max(ans,f[u]);
        }
    }
    for(auto v: g[u]) 
        if (v!=p) dfs1(v,u);
    if (u!=1) {
        fc[p]=tmp1;
        f[p]=tmp2;
        f[u]=tmp3;
    }
    
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    For(i,1,n-1) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    For(i,1,n) {
        char tmp;
        cin >> tmp;
        c[i]=tmp-'0';
    }
    dfs(1);
    if (c[1]) ans=max(ans,f[1]);
    dfs1(1);
    cout << ans;
    return 0;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6584 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6584 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6584 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -