Submission #307632

#	Time	Username	Problem	Language	Result	Execution time	Memory
307632		shafinalam	Power Plant (JOI20_power)	C++14	100 / 100	373 ms	27012 KiB

power

#include <bits/stdc++.h>
 
using namespace std;
 
const int mxn = 2e5+5;
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;
 
#define  sf scanf
#define  pf printf
 
#define  input freopen("in.txt","r",stdin)
#define  output freopen("out.txt","w",stdout)
 
#define  inf 1e18
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int arr[mxn];
vector<int>adj[mxn];
int dp[mxn];
int ans = 0;
void dfs(int u, int p)
{
    int mx = 0;

    for(auto v : adj[u])
    {
        if(v==p) continue;
        dfs(v, u);
        dp[u]+=dp[v];
        mx = max(mx, dp[v]);
    }
    if(arr[u])
    {
        ans = max(ans, mx+1);
        dp[u] = max(1, dp[u]-1);
    }
    ans = max(ans, dp[u]);


}
int main()
{
   // input;
    //output;

    int n;
    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);
    }
    string s;
    cin >> s;
    for(int i = 0; i < n; i++) arr[i+1] = s[i]-'0';
    dfs(1, 1);
    cout << ans << '\n';
    return 0;
}

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