Submission #1264284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264284		shiori_chan	Power Plant (JOI20_power)	C++20	100 / 100	104 ms	38928 KiB

power

#include <bits/stdc++.h>
using namespace std;

void dfs(int ind,int pros,vector<vector<int>>& sta,vector<vector<int>>& dp,vector<bool>& plant,int& najv){
   // cout << ind << "\n";
    cout.flush();
    for (int i=0;i<sta[ind].size();i++){
        int ind2=sta[ind][i];
        if (ind2==pros){
            continue;
        }
        dfs(ind2,ind,sta,dp,plant,najv);
    }
    if (!plant[ind]){
        int najv1=0;
        int najv2=0;
        for (int i=0;i<sta[ind].size();i++){
            int ind2=sta[ind][i];
            if (ind2==pros){
                continue;
            }
            najv1+=dp[ind2][0];
            najv2+=max(dp[ind2][0],dp[ind2][1]);


        }
        dp[ind][0]=najv1;
        dp[ind][1]=najv2;
        najv=max({najv,dp[ind][0],dp[ind][1]});
      //  cout << ind+1 << ":  " << najv1 << " " << najv2 << "\n";

    }
    else {

        int najv1=0;
        int najv2=0;
        int najv3=0;
        for (int i=0;i<sta[ind].size();i++){
            int ind2=sta[ind][i];
            if (ind2==pros){
                continue;
            }
            najv1+=dp[ind2][0];
            najv2+=max(dp[ind2][0],dp[ind2][1]);


        }
        najv3=najv1;
        for (int i=0;i<sta[ind].size();i++){
            int ind2=sta[ind][i];
            if (ind2==pros){
                continue;
            }
            najv3=max(najv3,najv1-dp[ind2][0]+dp[ind2][1]);
        }
        dp[ind][0]=najv1;
        dp[ind][1]=max(najv1+1,najv2-1);
        najv=max({najv,dp[ind][0],dp[ind][1],najv3+1});
     //   cout << ind+1 << ":  " << najv1 << " " << max(najv1+1,max(najv2-1,najv3+1)) << "\n";
    }


}

// 0 -> ti 0, oko tebe svi 0
// 1 -> ti 0, oko tebe jedan 1
// 2 -> ti 0, oko tebe svejedno
// 3 -> ti 1, oko tebe svi 0
// 4 -> ti 1, oko tebe jedan 1


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	#define task "task"
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".ans", "w", stdout);
	}

    int n;
    cin >> n;

    vector<vector<int>> sta(n,vector<int>{});
    for (int i=0;i<n-1;i++){
     //   cout << "a" << endl;
        int unos;
        int unos2;
        cin >> unos >> unos2;
        sta[--unos].push_back(--unos2);
        sta[unos2].push_back(unos);
       // cout << "b" << endl;
    }
    string s;
    cin >> s;
    vector<bool> plant(n,0);
    for (int i=0;i<n;i++){
        if (s[i]=='1'){
            plant[i]=1;
        }
    }
    int najv=0;
    vector<vector<int>> dp(n,vector<int>(2,0));
    dfs(0,0,sta,dp,plant,najv);
    cout << najv << "\n";
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 freopen(task".ans", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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