Submission #683851

#	Time	Username	Problem	Language	Result	Execution time	Memory
683851		victor_gao	Power Plant (JOI20_power)	C++17	100 / 100	175 ms	36444 KiB

power

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,have[N],dp[N],ans=0,root=1;
vector<int>g[N];
void dfs(int p,int lp){
    int tans=0,mx=0,cnt=0,mh=0;
    for (auto i:g[p]){
        if (i!=lp){
            dfs(i,p);
            tans+=have[i];
            mh=max(mh,have[i]);
            if (have[i]) cnt++;
            mx=max({mx,dp[i]});
        }
    }
  //  cout<<p<<" -> "<<mx<<" "<<mh<<' '<<tans<<" "<<have[p]<<'\n';
    dp[p]=max({mx,mh+have[p]});
    if (cnt<=1) dp[p]=max(dp[p],tans+have[p]);
    else dp[p]=max(dp[p],tans-have[p]);
    have[p]=max({have[p],tans-have[p],cnt-have[p]});
}
signed main(){
    fast
    cin>>n;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1;i<=n;i++){
        char c; cin>>c;
        have[i]=c-'0';
    }
    dfs(1,0);
  //  for (int i=1;i<=n;i++)
  //      cout<<dp[i]<<' ';
  //  cout<<'\n';
    cout<<dp[1]<<'\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53