Submission #1287192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287192		StefanSebez	Power Plant (JOI20_power)	C++20	100 / 100	234 ms	27868 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50;
vector<int>E[N];
int n,a[N];
int dp[N];
void DFS(int u,int p=0){
    int x=0;dp[u]=0;
    if(a[u])dp[u]=1,x=-1;
    for(auto i:E[u])if(i!=p){
        DFS(i,u);
        x+=dp[i];
    }
    dp[u]=max(dp[u],x);
}
int dp1[N];
void DFS1(int u,int p=0){
    int sum=0;
    for(auto i:E[u])if(i!=p)sum+=dp[i];
    for(auto i:E[u])if(i!=p){
        int x=0;dp1[i]=0;
        if(a[u])dp1[i]=1,x=-1;
        x+=dp1[u];
        x+=sum-dp[u];
        dp1[i]=max(dp1[i],x);
    }
    for(auto i:E[u])if(i!=p)DFS1(i,u);
}
int res=0;
void DFS2(int u,int p=0){
    int x=0;if(a[u])x=-1;
    x+=dp1[u];
    for(auto i:E[u])if(i!=p)x+=dp[i],DFS2(i,u);
    res=max(res,x);
}
int main(){
    scanf("%i",&n);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v);E[v].pb(u);
    }
    string s;cin>>s;
    for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    DFS(1);
    DFS1(1);
    DFS2(1);
    for(int i=1,num=0;i<=n;i++){num+=a[i];if(num<=2) res=max(res,num);}
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
power.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~

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