제출 #1364194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364194		ivaziva	Power Plant (JOI20_power)	C++20	47 / 100	85 ms	12708 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001
#define int long long

int n;vector<int> adj[MAXN];
int dist[MAXN],parent[MAXN];
vector<int> switches;
set<int> on,breakovani;
int dp[MAXN];string s;

void calculate(int node,int pret)
{
    int children=0;
    for (int sled:adj[node])
    {
        if (sled==pret) continue;
        calculate(sled,node);
        children+=dp[sled];
    }
    if (s[node-1]=='0') dp[node]=max(children,(long long)0);
    else dp[node]=max(children-1,(long long)1);
}

int32_t main()
{
   cin>>n;for (int i=1;i<n;i++) {int u,v;cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}
   cin>>s;
   if (n<=2000)
   {
       int answer=0;
       for (int node=1;node<=n;node++)
       {
           if (s[node-1]=='1') answer++;
       }
       if (answer<=2) {cout<<answer<<endl;return 0;}
       answer=0;
       for (int root=1;root<=n;root++)
       {
           for (int node=1;node<=n;node++) dp[node]=0;
           calculate(root,0);answer=max(answer,dp[root]);
       }
       cout<<max(answer,(long long)2)<<endl;return 0;
   }
   return 0;
}

• 서브태스크 1: 6 / 6
• 서브태스크 2: 41 / 41
• 서브태스크 3: 0 / 53