제출 #1264284

#제출 시각아이디문제언어결과실행 시간메모리
1264284shiori_chanPower Plant (JOI20_power)C++20
100 / 100
104 ms38928 KiB
#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"; }

컴파일 시 표준 에러 (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);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...